GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
354 views
Given an array of $n$ elements find the maximum continuous sum in it. For example consider the below array of $n=6$.

23 4 -10 2 15 1

Answer is 35.
asked in Algorithm Challenges by Veteran (289k points)  
edited by | 354 views

ok....sir...i will be upload the correct solution...smiley

See my answer and then code. Because there is no advantage in solving this question correctly- key is to solve all such questions correctly :)
ok i got  the idea from ur answer sir...i will try it .
See again, I had written wrong earlier :O
@Arjun sir please check out this one if that will work.

 

#include <stdio.h>

int main(void) {
   int n;
   int i;
   int sum = 0;
   int max = 0;
   int *arr = malloc(sizeof(int)*n);
   scanf("%d",&n);
   for(i = 0; i<n; i++){
       scanf("%d ",&arr[i]);
   }
   
   for(i = 0; i<n;i++){
           sum+=arr[i];
           if(sum<0) sum = 0;
           if(max<sum) max = sum;
   
   }
   
   printf("%d",max);
    return 0;
}

2 Answers

+1 vote

I asked this question to explain dynamic programming. I hope question is clear. Okay now, our challenge is to find the start and end of a subarray in the given array so that sum is maximum. i.e., given array

$$A[1..n]$$,

we have to find $i$ and $j$ such that $\sum_{k=i}^j A[k]$ is maximum. (Well, we don't need to output $i$ and $j$ but just the corresponding sum).

Okay, so one important thing is we are looking at "subarray" and not "subsequence" and hence the elements in the required subarray must be continuous. This makes the problem harder (subsequence solution will just be the sum of all positive array numbers).

Now, lets see if the problem has any sub-part which can be solved and which overlaps (if so we can do dynamic programming).

So, let me take an array element - say $A[i]$. There are only 2 choices for it- either it is in the required subsequence or it is not. So what is the condition for inclusion?

  1. Let us assume the array ends at i for now.
  2. We include A[i] in our required subarray, if the sum of the subarray ending at i-1 + A[i] produces a sum greater than any other subarray.

Well, the second statement here is the key- it gives our problem sub problems and moreover they are overlapping. So, lets try to apply it. What we need is an array say "sum" to store the max continuous sum for each position of the array ($sum[i]$ gives the maximum sum of the substring ending at $i$)  and one more element say MAXS, which stores the max sum seen so far. Now, we can say

sum[i] = max(sum[i-1] + A[i], A[i]);
if (sum[i] > MAXS), MAXS = sum[i];

with sum[1] = A[1] and MAXS = A[1] as the boundary conditions. 

Now, trying to code this? - 10 lines? :P

answered by Veteran (289k points)  
edited by
ok sir.. i hav checked again...u made earlier sum[i] = max(MAXS,sum[i-1] + A[i]]);

now ..it is.... sum[i] = max(sum[i-1] + A[i], A[i]);...rt?
yes. And unfortunately that is the MOST important step and what I wanted to say :(
arjun sir, scroll back to check by answer i have updated it...u plz check the dynamic prgamming is correctly implemented in program or not.
yes, it looks correct :)

yes..i hav done in less than 10 linessmiley

0 votes
answered by (201 points)  


Top Users Jul 2017
  1. Bikram

    5784 Points

  2. manu00x

    3602 Points

  3. Arjun

    1988 Points

  4. Debashish Deka

    1924 Points

  5. joshi_nitish

    1908 Points

  6. pawan kumarln

    1680 Points

  7. Tesla!

    1426 Points

  8. Hemant Parihar

    1334 Points

  9. Shubhanshu

    1180 Points

  10. Arnab Bhadra

    1124 Points


24,169 questions
31,186 answers
71,039 comments
29,512 users