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

import java.util.*;


public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        // 题目要求返回长度最长的一个，则需要使用left、right记录子数组的起始
        // 需要更新最大值的时候（要么子数组和最大，要么子数组和相等下区间要更长）顺便更新最终的区间收尾，这样来维护子数组的长度是最长的
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int maxsum = dp[0];
        // 滑动区间
        int left = 0, right = 0;
        // 记录最长的区间
        int resl = 0, resr = 0;
        for(int i = 1;i<array.length;i++){
            right++;
            // 用dp数组表示以下标i为终点的最大连续子数组和，则每次遇到一个新的数组元素，连续的子数组要么加上变得更大，要么它本身就更大
            dp[i] = Math.max(dp[i-1]+array[i],array[i]);
            // 区间新起点
            if(dp[i - 1] + array[i] < array[i]){
                left = right;
            }
            // 更新最大值
            if(dp[i] > maxsum || dp[i] == maxsum && (right - left + 1) > (resr - resl + 1)){
                maxsum = dp[i];
                resl = left;
                resr = right;
            }
        }
        int[] res = Arrays.copyOfRange(array,resl,resr+1);

        return res;
        
    }
}