The Gateway to Computer Science Excellence

+2 votes

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.

23 4 -10 2 15 1

Answer is 35.

0

*algorithim ///////////dynamic programming*

*A[n] is array that contains elements *

* maxms = A[1]; //maxms stores the highest sum seen*

* void sum(n)*

*{ *

* if(n==1) MCS[1] = A[1]; ///MCS[n] =is a array stores calculated sum *

* ///short of "maximum continous sum"*

*MCS[n] = sum(n-1)+ A[n];*

*if (MCS[n] < A[n]) MCS[n] = A[n];*

*if(maxms < MCS[n] ) maxms = MCS[n] ;*

*return maxms; ////////finally it will return maximum sum*

*}*

*sir...check it ....correct me if any error.*

0

sir ...if the answer is 60...the above code..won't work..////.u plz tell...i had this confusion....can we neglect...all the starting elements..and chose..the last element...and still it is continous???

0

yes...i did overwrite it...my mistake...check it now...i just want...copy all elements of array 'a' to array 'b'...after the continous sum so that if...any individual array element is big enough from...continous sum..then it should be selected..

0

Well, this is going like a placement interview :D So, next input:

10 20 -35 60 1

Given answer will be 60 rt?

Okay, do not try to correct your code- because there is an algorithmic decision you have to make. What we have to find is the start and end of the subarray. See how we can do this.

10 20 -35 60 1

Given answer will be 60 rt?

Okay, do not try to correct your code- because there is an algorithmic decision you have to make. What we have to find is the start and end of the subarray. See how we can do this.

0

sorry...i took ur so much time...i only will solve it ....u just give some time/days with correct code..

0

yes, this is an issue of programmers- even I always used to correct the code and not think of the algorithm. Since you are a good explainer you can try explaining your code and when you do, you should get the correct solution also :) The only thing here is to find the start and end of the subarray. But I'll give a solution without finding this.

0

See my answer and then code. Because there is no advantage in solving this question correctly- key is to solve all such questions correctly :)

0

@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;

}

#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;

}

+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?

- Let us assume the array ends at i for now.
- 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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,834 questions

57,852 answers

199,512 comments

108,375 users