Content deleted Content added
mNo edit summary |
|||
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==
| |||