search
Log In
11 votes
5.7k views
Consider a sequence of $14$ elements: $A=[-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]$. The sequence sum $S(i,j) = \Sigma_{k=i}^j A[k]$. Determine the maximum of $S(i,j)$, where $0 \leq i \leq j <14$. (Divide and conquer approach may be used.)

Answer: ___________
in Algorithms
edited by
5.7k views

6 Answers

19 votes
 
Best answer

Subsequence :  A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Subarray : A subarray of n-element array is an array composed from a contiguous block of the original array's elements.

Question is asking for subsequence.

$S(i,j) = \sum_{k=i}^j A[k]$
 

What does $\sum_{k=i}^j $ mean? It means you start from index $i$ and go till index $j$ with unit increment each time.

Ultimately they are asking 'Maximum subarray sum'.

int maxsum = A[0], sum = A[0], n=14;
for(int i=1; i<n; i++){
    if (A[i]>A[i-1) {
        if (sum > 0) sum+=A[i];
        else sum = A[i];
    }
    else sum = A[i];
    if (maxsum < sum) maxsum = sum;
}

 

sum $=6 + 3 - 1 - 2 + 13 + 4 - 9 - 1 + 4 + 12 = 29$


selected by
0
Divide and Conquer may be used ??

how we can apply in the question ???
2

@kumar.dilip
 

It's just to know the answer. Divide and Conquer doesn't need here this case because noticing the array watchfully, we can find maximum subarray sum. See Kadane’s Algorithm.

0
Why the second last element i.e -3 left for addition?
12 votes
29 for the the subsequence (6, 3, -1, -2, 13, 4, -9, -1, 4, 12)

Use kadanes algorithm or mental brute force is good to go with !!!
0
What is the difference between subsequence and subarray?
0

What is the difference between subsequence and subarray ???

Please explain ??

 

0

@ sir @ sir Can't we sort the array (using D & C) & then sum all +ve integer to get maximum value??

0
if there are n elements in the list then

$2^{n}.$ will be.

Here talking about subsequence sub not subarray sum ??

then should be 42  ??
0
They have defined the definition of subsequence in question explicitly. So it should be clear from that.
0
can't we use merge sort & then perform subsequence sum a/c to given question?
0

I'm not getting you sir. Please explain.

0

There is noting the word contiguous in the question ???

42 should be the answer because they are talking about subsequence.

 

0
I too got 42
0

@kumar.dilip

what is the definition of s(i,j) in the question ?

0
we can sort the given list ???
1

@kumar.dilip

u have to find the maximum in a continuous run, u cant skip some of the values in the middle

0

what's meaning of divide and conquer there ??

0
It is one of the algorithms paradigms..
0

what's wrong here?? By using D & C :-

0

@Naveen Kumar 3

Did you mean, " Divide and conquer = Sorting " ?

0

I thought the same. What does it mean @Shaik sir?

1

Divide & conquer

Greedy

Dynamic Programming

all these are algorithm design paradigms, you can use these paradigms while solving your problem !

ex:- problem is sorting but paradigm may be Divide & conquer or Greedy or Dynamic.

 

For this question :- problem is " Finding maximum sub array sum ", paradigm may be use Divide & conquer.

https://www.geeksforgeeks.org/maximum-subarray-sum-using-divide-and-conquer-algorithm/

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

3 votes
Taking 6 to 12 the largest sum will be 29.

While trying to take positives, negatives also need to be taken so sum shrinks to 29.
1 vote
Logic: as pattern can be seen, it's consecutive positives and consecutive nevatiy.

So 1st two and last two are to be ignored for sure.

Combine remaining as pairs of two as if 1 positive counted then next also, if one negative ignored other shall also be.

This way I made pairs out of it as below:

-15, 9, -3, 17,-12,16,-3.

Now check all three middle combination.

I got 29
1 vote
Just by observation, the subsequence with the maximum sum would be from 6 to 12.

So, $6+3−1−2+13+4−9−1+4+12$

=> $29$.
0 votes
There is a basic DP problem, which can be formulated as follow:

Let $S[i]$ be the maximum sum till the $ith$ index.

The answer we are looking for is $S[n]$ i.e the maximum sum that is possible till the last index.

Now, the recursion for the DP can be written as follows:

$S[i] = max(S[i-1] + a_i, S[i-1])$

The first term refers to the fact when the element we add is positive and adds to the sum, the second term is used when the current term doesn't do us any favour.

Using this, the answer can be easily found out to be 29.
Answer:

Related questions

15 votes
5 answers
1
5.2k views
An array of $25$ distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to $2$ decimal places) is ________
asked Feb 7, 2019 in Algorithms Arjun 5.2k views
35 votes
8 answers
2
3.8k views
There are $5$ bags labeled $1$ to $5$. All the coins in a given bag have the same weight. Some bags have coins of weight $10$ gm, others have coins of weight $11$ gm. I pick $1, 2, 4, 8, 16$ coins respectively from bags $1$ to $5$ Their total weight comes out to $323$ gm. Then the product of the labels of the bags having $11$ gm coins is ___.
asked Sep 28, 2014 in Algorithms jothee 3.8k views
13 votes
8 answers
3
6.3k views
The following C program is executed on a Unix/Linux system : #include<unistd.h> int main() { int i; for(i=0; i<10; i++) if(i%2 == 0) fork(); return 0; } The total number of child processes created is ________________ .
asked Feb 7, 2019 in Operating System Arjun 6.3k views
4 votes
5 answers
4
4k views
Consider the following C program : #include<stdio.h> int jumble(int x, int y){ x = 2*x+y; return x; } int main(){ int x=2, y=5; y=jumble(y,x); x=jumble(y,x); printf("%d \n",x); return 0; } The value printed by the program is ______________.
asked Feb 7, 2019 in Programming Arjun 4k views
...