题解 | Java O(1)空间 #连续子数组的最大和(二)# [P2-T2]

假dp 思路和连续子数组的最大和一模一样的
只需要多记录当前最优解的长度和endingIndex(为了在Sum相同的情况下比较长度，和之后还原SubArray).
这里把global和local的GSS的参数存成两个int[3]。具体逻辑看comment。

时间：O(n), 每个数visit一次
空间：O(1), 两个int[3].

import java.util.*;


public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
      if (array.length <= 1) return array;
      
      // let GSS be the longest GreatestSumSequence
      // gss[0]: GSS sum
      // gss[1]: GSS ending index
      // gss[2]: GSS length 
      int[] gss = new int[] {array[0], 0, 1};  // global gss
      // gss ending with the current number
      int[] cur = new int[] {array[0], 0, 1};  // local gss
      
      for (int i = 1; i < array.length; i++) {
        if (cur[0] >= 0) {
          // previous cur.sum >= 0, should concat
          cur[0] += array[i];
          cur[1] = i;
          cur[2] += 1;
        } else {
          // gss ending with array[i] is just { array[i] }
          cur[0] = array[i];
          cur[1] = i;
          cur[2] = 1;
        }
        
        if (cur[0] > gss[0]) {
          // larger sum, update global gss to cur
          gss = Arrays.copyOf(cur, 3);
        } else if (cur[0] == gss[0] && cur[2] > gss[2]) {
          // same sum, longer length, update global gss to cur
          gss = Arrays.copyOf(cur, 3);
        } // else do nothing
      }
      
      int endIdx = gss[1];
      int gssLen = gss[2];
      // note: copyOfRange是左开右闭
      int[] ans = Arrays.copyOfRange(array, endIdx-gssLen+1, endIdx+1);
      return ans;
    }
}