vlambda博客
学习文章列表

FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
left_sum = -INFsum = 0for i = mid downto low    sum = sum + A[i]    if sum > left_sum       left_sum = sum       max_left = iright_sum = -INFsum = 0for j = mid+1 to high    sum = sum+A[j]    if sum > right_sum       right_sum = sum       max_right = jreturn(max_left,max_right ,left_sum+right_sum)

FIND-MAXIMUM-SUBARRAY(A,low,high)
if high == low     //base case  return(low,high,A[low])else   mid = (low+high)/2  (left_low,left_high,left_sum) = FIND-MAXIMUM-SUBARRAY (A,low,mid)  (right_low,right_high,right_sum) = FIND-MAXIMUM-SUBARRAY (A,mid+1,high)  (cross_low,cross_high,cross_sum) = FIND-MAX-CROSSING-SUBARRAY (A,low,mid,high)  if left_sum >= right_sum and  left_sum >= cross_sum     return (left_low,left_high,left_sum)  else if right_sum >= left_sum and       right_sum >= cross_sum     return (right_low,right_high     ,right_sum)  else return(cross_low,cross_high       ,cross_sum)

Kadane's algorithm
int max_so_far = a[0];int max_ending_here = a[0];
for (int i = 1; i < size; i++){ max_ending_here = Math.max(a[i], max_ending_here+a[i]); max_so_far = Math.max(max_so_far, max_ending_here);}return max_so_far;