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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        int[] dp = new int[array.length];//当前位置子数组和的最大值
        int[] len = new int[array.length];//当前位置最大子数组的长度
        dp[0] = array[0];
        len[0] = 1;
        int max = array[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]){
                len[i] = len[i - 1] + 1;
            }else {
                len[i] = dp[i] == array[i] ? 1 : len[i - 1] + 1;
            }
            max = Math.max(max,dp[i]);
        }
        int index = -1;
        Queue<int[]> queue = new PriorityQueue<>(1,(x,y) -> {
            return y[1] - x[1];
        });
        for (int i = 0; i < array.length; i++) {
            if(dp[i] == max){
                int[] ints = new int[2];
                ints[0] = i;
                ints[1] = len[i];
                queue.add(ints);
            }
        }
        index = queue.peek()[0];
        int[] res = new int[len[index]];
        int j = 0;
        for (int i = index - len[index] + 1; i <= index; i++) {
            res[j] = array[i];
            j++;
        }
        return res;
    }
}

一个dp数组存最大和，一个长度数组存最大数组长度，然后直接根据下标和长度从原数组里摘出来就行（可能有多个数组和都是最大，用优先队列排个序就行）