题目主要信息

1、给一个长度为n为整型数组

2、找出具有最大和的连续子数组

3、如有多个，选最长的

方法一:动态规划

具体方法

本题和JZ42题基本类似，区别在于需要输出具体的最大和的连续子数组，并且选择其中长度最长的。 首先，对于JZ42题，我们使用动态规划的方法，令f[x]为x为右侧边界的子数组的最大和。

则f[x] = max(f[x-1] + array[x], array[x])

其次，为了记录具体的数组内容，并且找到其中最长的子数组，我们需要几个变量进行存储我们找到的子数组的信息，可以通过三个变量来具体确定，最大和、右侧边界、最大长度，即可。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int max = array[0];  //最大和
        int index = 0;  //最优子数组右坐标
        int maxlen = 0;  //最大长度
        int len = 0;  //当前长度
        int[] dp = new int[array.length + 1];
        for(int i=1; i<=array.length; i++){
            dp[i] = Math.max(dp[i-1]+array[i-1], array[i-1]);
            if(dp[i-1] + array[i-1] >= array[i-1]){
                len+= 1;
            }else{  //重置长度
                len = 1;
            }
            if(dp[i] > max || (dp[i]==max && len>maxlen)){  //更新最新值
                index = i;
                maxlen = len;
                max = dp[i];
            }
        }
        int[] ans = Arrays.copyOfRange(array, index-maxlen, index);
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，单循环
• 空间复杂度：$O(n)O(n)$，动规数组长度为n

方法二:动态规划（空间压缩）

具体方法

由于在状态转移过程中，当前的最大和只和前一个元素的最大和相关，因此进行动规数组的空间压缩，用pre来表示前一个元素的最大和即可。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int max = array[0];  //最大和
        int index = 0;  //最优子数组右坐标
        int maxlen = 0;  //最大长度
        int len = 0;  //当前长度
        int pre = Integer.MIN_VALUE;
        int now;
        for(int i=1; i<=array.length; i++){
            if(pre>=0){
                now = pre+array[i-1];
                len+= 1;
            }else{  //重置长度
                now = array[i-1];
                len = 1;
            }
            if(now > max || (now==max && len>maxlen)){  //更新最新值
                index = i;
                maxlen = len;
                max = now;
            }
            pre = now;
        }
        int[] ans = Arrays.copyOfRange(array, index-maxlen, index);
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，单循环
• 空间复杂度：$O(1)O(1)$，常数空间