maximum subarray sum code example
Example 1: kadane algorithm
public int kadane(int[] arr){
int max_so_far = 0, curr_max = Integer.MIN_VALUE;
for(int i: arr){
max_so_far += i;
if(max_so_far<0) max_so_far = 0;
if(max_so_far>curr_max) curr_max = max_so_far;
}
return curr_max;
}
Example 2: max subsequence sum in array
def max_subarray(numbers):
"""Find the largest sum of any contiguous subarray."""
best_sum = 0
current_sum = 0
for x in numbers:
current_sum = max(0, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
Example 3: kadane algorithm actual
//Kadene's algorithm where empty array is allowed.
int ms,cs;
ms=cs=0;
for(int i=0;i<n;i++)
{
cs=cs+a[i];
if(cs<0)
{
cs=0;
}
ms=max(ms,cs);
}
cout<<ms<<endl;
}