GATE CSE 2019 | Question: 25

Question

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: ___________

Comments

https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/

for [−5,−10,6,3,−1,−2,13,4,−9,−1,4,12,−3,0]

[-5,-15,-9,-6,-7,-9,4,8,-1,-2,2,14,9,9] will be prefix sum array.

Difference between sums will give us range sum queries (on the prefix sum array)

Eg: Arr = [a,b,c,d,e]
Prefix sum = [a,a+b,a+b+c,a+b+c+d,a+b+c+d+e]

Arr[1] + (PrefixSum[4] – PrefixSum[1]) = b+c+d+e  //Sum between 1 and 4

Hence, to maximize sum, find the maximum difference, which is clearly between 14 and -15 in our prefix array.
14-(-15) = 29, which will be the final answer.
 

---

[-5,-15,-9,-6,-7,-9,4,8,-1,-2,2,14,9,9] will be prefix sum array.  

 I think here the last two indexes values should be 11,0 instead of 9,9. 

---

if the Sigma notation would not been given then the subsequence sum would have been sum of all positive numbers

Answer 1

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$

Comments

As in question they clearly mentioned that DAC may be used ...so why we are using kaden’s algo here...although it will not affect the answer..but it will affect the time complexity in a significant manner .. so if time complexity was asked instead of sum…..and DAC mentioned then do we have to give TC as O(nlogn) or by considering kaden’s algo  we have to give it as O(n)..

anyone?

---

@Pranavpurkar We have to give time complexity as O(nlogn) as question is asking about divide and conquer.

---

If I consider the subsequence: 6,3,13,4,4,12,0. So this is also the subsequence right? So if I consider it, then the answer should be 42. What's wrong in this approach?

Answer 2

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 !!!

Comments

yes mental bruteforce worked for me

I solved it correctly in GATE 2019

---

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.

---

here we cannot change the position of elements in an array sorting won’t work

Answer 3

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.

Answer 4

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$.