Largest contiguous sum

Computer Science Level 5

Given an unsorted array of numbers, compute the largest contiguous subset sum in the array.

What is the largest contiguous sum in the text .

Details and Assumptions

For example in the array [2, -2, -1, 5, 4] the largest such sum is 9 9 .... [5,4]

Here is an easier problem.


The answer is 4971.

View wiki
Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Samarpit Swain
Nov 24, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// A solution in C++ using DP( Complexity: O(n) )

#include<iostream>
#include<algorithm>
using namespace std;

 int Max(int x, int y)
 {
  if(x>y)

     return x;
  else

  return y;
 }     

int LargestSum(int dp[], int n)
{
int largeI = dp[0];
int largeF = dp[0];

for (int i = 1; i<n; i++) // n= sizeof(dp)/sizeof(dp[0]);
{
        largeI = Max(dp[i], largeI+dp[i]);
        largeF = Max(largeF, largeI);
}
  return largeF;
 }

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Pranjal Jain
Nov 21, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 
int MaxSumSubArray(vector<int>M)
{
    int N=M.size(),i,t=0,S=1<<31;
    for (i=0;i<N;i++)
    {
        t=t+M[i];
        S=max(t,S);
        if (t<0)
           t=0;
    }
    return S;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Arulx Z
Aug 13, 2015 
1
2
3
4
5
6
 
>>> lar = 0
>>> for x in xrange(0, 9999):
        for y in xrange(0, 10000 - x):
            summ = sum(array[y : y + x])
            lar = summ if summ >  lar else lar
>>> print lar

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

How can we improve on this algorithm? Is there a much faster approach?

This is a trivial O ( N 2 ) O(N^2) solution. Can you think of a faster O ( N ) O(N) algorithm ? Hint: Dynamic Programming!

Abhishek Sinha - 5 years, 10 months ago

Log in to reply

Thanks for your comment. I'll surely try to improve my solution.

Arulx Z - 5 years, 10 months ago

Can you please suggest a good book or website about dynamic programming to continue my reading? I couldn't find any helpful information through my searches.

Arulx Z - 5 years, 10 months ago

Log in to reply

One of the best elementary book on Dynamic Programming is this one by Prof. Bertsekas.

Abhishek Sinha - 5 years, 10 months ago

Log in to reply

@Abhishek Sinha – Thanks a lot!

Arulx Z - 5 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...