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

JZ85 连续子数组的最大和（二）M

描述：输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。

解：在上题的基础上，本体需要返回最大子数组的序列。动态规划的记录最大子数组和的同时，需要记录最大子数组的开始、结束下标。每次重新定位最大子数组前，判断当前子数组和是否比记录的最大值大或者值相同但更长，如满足条件就更新下标。

**优化：**思路同上题优化，当前空间复杂度为O(n)，主要用于数组记录以当前位置为末尾的子数组的最大子数组和。将其改为int跟随记录即可，空间复杂度为O(1)。

import java.util.*;

public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        if (array.length == 0) {
            return new int[0];
        }
        //记录当前连续数组的开始和结束下标
        int start = 0, end = 1;
        //max记录整个数组中最大的子数组和；sum记录以array[i-1]为末尾数组的连续子数组最大和
        int max = Integer.MIN_VALUE, sum = array[0];
        //res记录当前和最大的子数组开始、结束下标
        int res = 0, ree = 1;
        
        for (int i = 1; i < array.length; ++i) {
            if (array[i] > sum + array[i]) {
                sum = array[i];
                start = i;
                end = i + 1;
                if (sum > max || sum == max && ree - res < end - start) {
                    res = start;
                    ree = end;
                    max = sum;
                }
            } else {
                sum = sum + array[i];
                end = i + 1;
                if (sum > max || (sum == max && end - start > ree - res)) {
                    res = start;
                    ree = end;
                    max = sum;
                }
            }
        }
        return Arrays.copyOfRange(array, res, ree);
    }
}