retagged by
2,977 views
2 votes
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.
retagged by

2 Answers

1 votes
1 votes

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

edited by

Related questions

1 votes
1 votes
1 answer
1
radha gogia asked Apr 10, 2016
2,032 views
According to me first we sort the array in O(nlogn) time and then in O(k) time , find the product , so total time complexity is O(nlogn) , so am I right or can it be done...
0 votes
0 votes
0 answers
2
Arjun asked Jun 6, 2016
1,053 views
Given an arithmetic expression involving *, + only write an object oriented code for its representation and evaluation
1 votes
1 votes
0 answers
3
Arjun asked Jun 6, 2016
449 views
Write an object oriented code for representing boolean expressions and then a function for checking the equivalence of two boolean expressions.
2 votes
2 votes
1 answer
4
Arjun asked Apr 9, 2016
1,348 views
You are given a number lock of 4 digits and it accepts a serial input. What should be the minimum length of an input string so that the lock is guaranteed to open assumin...