Maximum Interval Sum

• 定義給n個整數num[0..n-1]，maximum interval sum要求 0<=i<j<=n-1，
  sum = num[i]+...+num[j]中最大那一個
  
• 作法: sweep from left to right, accumulate the sum one element by one
  element, start new interval whenever you encounter partial sum<0 (and record
  current best maximum interval encountered so far)
  
• 範例:

  num: 4 -5 4 -3 4 4 -4 4 -5
  sum: 4 -1 4  1 5 9  5 9  4

• 解釋，對某一個位置k, sum[k]要根據sum[k-1]決定要不要累加sum[k-1],
  如果sum[k-1]小於0, 捨棄, 從位置k開始累加, 如果大於0, 把sum[k-1]累加.
• code:
  

  max = sum[0] = num[0];
  for(i=1 ; i<n ; i++) {
      if(sum[i-1] < 0)
          sum[i] = num[i];
      else
          sum[i] = sum[i-1] + num[i];
      if(sum[i] > largest)
          max = sum[i];
  }

  
  
• 練習題: 507 - Jill Rides Again, 10684 - The Jackpot

tag: acm programming