题解 | #连续子数组的最大和(二)#

import java.util.*;
public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        //记录到下标i为止的最大连续子数组和的最大值
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int maxsum = dp[0];
        //滑动区间
        int pre = 0;//左边是pre，右边是i，即当前的位置
        //记录最长的区间
        int resLeft = 0, resRight = 0;
        for (int i = 1; i < array.length; i++) {
            //状态转移：连续子数组和最大值
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);

            //区间新起点
            if (dp[i - 1] + array[i] < array[i])
                pre = i;
            
            
            //更新最大值
            if (dp[i] > maxsum || dp[i] == maxsum &&
                    (i -pre + 1) >= (resRight - resLeft + 1)) {
                maxsum = dp[i];
                resLeft = pre;
                resRight = i;
            }


        }
        //取数组
        int[] res = new int[resRight - resLeft + 1];
        for (int i = resLeft; i <= resRight; i++)
            res[i - resLeft] = array[i];
        return res;
    }
}