Contiguous sequence with the largest sum.

You are given an array of integers(both positive and negative). Find the contiguous sequence with the largest sum. Return the sum.

C++:
01 int largestSum(int *A, int size)
02 {
03     int max=A[0];
04     int start=0;
05     while(start<size){
06         int tmp=0;
07         for(int i=start;i<size;i++){
08             tmp+=A[i];
09             if(tmp>max)
10                 max=tmp;
11             if(tmp<0){
12                 start++;
13                 break;
14             }
15         }
16     }
17     return max;
18 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s