retagged by
19,035 views
23 votes
23 votes
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: ___________
retagged by

9 Answers

Best answer
31 votes
31 votes

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 (sum > 0) sum+=A[i];
     else sum = A[i];
    }
    if (maxsum < sum) maxsum = sum;
}

 

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

edited by
17 votes
17 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 !!!
3 votes
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.
2 votes
2 votes
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$.
Answer:

Related questions

29 votes
29 votes
4 answers
1
24 votes
24 votes
8 answers
2
Arjun asked Feb 7, 2019
17,134 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 ...
13 votes
13 votes
4 answers
3
Arjun asked Feb 7, 2019
9,564 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"...
17 votes
17 votes
3 answers
4