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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // 要定位出dp[]最大时 array[]对应的起始位置
        //定义dp数组
        int[] dp = new int[array.length];

        //初始值
        dp[0] = array[0];

        //最大值 注意不是0
        int result = array[0];
        int left = 0,right = 0;
        
        //记录最长区间
        int resl = 0, resr = 0;

        //遍历方式
        for (int i = 1; i < array.length ; i++) {
            //保证右边界每次循环+1 有可能起点一样但两个长短不一的数组最大值相同
            right++;

            //递归逻辑
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);

            //更新起点 起点肯定从array[i]比现=先前数组大的时候开始
            //反向思考：如果起点左移一位 整个数组就缩小了 所以必然不会左移
            if(dp[i - 1] + array[i]<array[i] ) {
                left = i;
                            
            }

            //保存最大值 有时候数组长度拉长 总和还是不变 要得出最长的数组
            if (result < dp[i] || (dp[i] == result && (right - left )>(resr - resl))){
                result = dp[i];
                resl = left;
                resr = right; 
                
            } 
        }

        int[] res = new int [resr -resl +1];

        for(int i = 0;i<=resr -resl;i++){
            res[i] = array[i+resl];
        }

        return res;
    }
}