Algoritmo de kadane

Contiguous subarray with largest sum (Kadane): Dynamic Programming

Given an array of signed integers, find a subarray with largest sum in that array. Subarray is continuous indices of array with size ranging from 0 to N where  N is size of original array.

For example, for array {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3} maximum sum sub array will be {4,6,-1,2,-7,13} with sum = 17

Largest sum subarray problem is solved using Kadane’s algorithm.

look at this link, it gives a clear explanation for Kadane's algorithm. Basically you have to look for all positive contiguous segments of the array and also keep track of the maximum sum contiguous segment until the end. Whenever you find a new positive contiguous segment, it checks if the current sum is greater than the max_sum so far and updates that accordingly. The following code handles the case when all the numbers are negative. int maxSubArray(int a[], int size) { int max_so_far = a[0], i; int curr_max = a[0]; for (i = 1; i < size; i++) { curr_max = max(a[i], curr_max+a[i]); max_so_far = max(max_so_far, curr_max); } return max_so_far; }

otro con analisis de alternativas

http://www.ritambhara.in/kadanes-algorithm-to-find-maximum-subarray-sum/