Maximum subarray problem: Difference between revisions

Revision as of 17:39, 7 October 2010

Revision as of 18:19, 7 October 2010

Line 16:

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem, the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of [[dynamic programming]].

Code expressed in C++ below:

<source lang="python">

#include <iostream>

using namespace std;

int main()

{

int max_so_far = 0,max_ending_here =0;

int A[] = {14,-15,6,-3,2,3,4,5,-1};

for(int i=0;i<9;i++){

max_ending_here = (max_ending_here + A[i])>0?max_ending_here + A[i]:0;

max_so_far = max_ending_here>max_so_far?max_ending_here:max_so_far;

}

cout<<"Maximum sum::"<<max_so_far<<endl;

}

</source>

==Generalizations==