DP求解 最大连续子数组和_连续数组和dp

DP求解 最大连续子数组和

题目描述：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

1. 暴力求解

思路分析：计算数组中每一个连续子数组的和，找出其中最大值

 /**
     * 暴力求解
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums)
    {
        int sum, max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++)
        {
            //每次从头开始加，sum归0
            sum = 0;
            for (int j = i; j < nums.length; j++)
            {
                //每次加一个相当于新的子数组
                sum += nums[j];
                //记录最大值
                if (sum > max)
                {
                    max = sum;
                }
            }
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

数据量较小时运行无异常，当数据量过大时，测试将会超时！

2. 动态规划

思路分析：

假设dp[i] 代表以元素 nums[i]为结尾的连续子数组最大和，对于dp[i]的值有两种情况

• 当dp[i-1]<=0时，那么**num[i]+dp[i-1]**一定小于num[i]本身，这时如果要求以nums[i]为结尾的连续子数组的最大值，肯定不要其前面的数组，那么dp[i]=nums[i];

  例：[-2,1], 显而易见 dp[0]= -2，那么以1为结尾的连续子数组和，可以是前两者之和 -1 ，也可以只是第二项1，如果是前两者之和，那么肯定小于等于第二项本身(加了个非正数)，所以最大肯定为第二项本身，dp[1]=nums[1]=1。

• 当dp[i-1]>0时, 那么num[i]+dp[i-1]一定大于num[i]本身，这时如果要求以nums[i]为结尾的连续子数组的最大值，肯定要其前面的数组，那么dp[i]=nums[i]+dp[i-1];

  例：[2,1], 显而易见 dp[0]= 2，那么以1为结尾的连续子数组和，可以是前两者之和 3，也可以只是第二项1，如果是前两者之和，那么肯定大于第二项本身(加了个正数)，所以最大肯定为dp[1]=nums[1]+dp[0]=3。

综上：当dp[i-1]<=0时 dp[i]=nums[i]

​ 当dp[i-1]>0时，dp[i]=nums[i]+dp[i-1]

最终构建完dp数组后，其中最大值便是最大连续子数组和

代码如下：

public static int maxSubArray(int[] nums)
{
    //dp[i] 代表以元素 nums[i]为结尾的连续子数组最大和
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    for (int i = 1; i < nums.length; i++)
    {
        //如果dp[i-1]>0,那么加上当前值，将会使当前值增大
        if (dp[i - 1] > 0)
        {
            dp[i] = dp[i - 1] + nums[i];
        }
        else
        {
            //如果dp[i-1]<=0,那么加上当前值，将会使当前值减小(不变)，那么还没有本身大，所以直接等于本身即可
            dp[i] = nums[i];
        }
        //以上if判断实际就是找两个的较大值，所以可以直接用下面这个代替
        //dp[i] = Integer.max(dp[i] = dp[i - 1] + nums[i], dp[i] = nums[i]);
    }
    int res = nums[0];
    //找出dp数组中的最大值
    for (int i = 1; i < dp.length; i++)
    {
        if (dp[i] > res)
        {
            res = dp[i];
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3. 动态规划 优化

优化1：由于dp[i] 只与 dp[i - 1] 和 nums[i] 有关，所以用两个参数存储循环过程中的dp[i]和dp[i-1]的值即可

优化2：之前使用循环找出dp数组中的最大值，可以使用一个max在循环中来记录最大值即可

综上，代码如下

public static int maxSubArray(int[] nums)
{
    int max = nums[0];//初始情况下最大值为第一个数本身
    int per = 0;//用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0
    int cur;//记录当前值
    for (int num : nums)
    {
        cur = num;//当前值
        int curMax = Integer.max(cur, cur + per);//判断前者大，还是当前加上前者大
        max = Integer.max(max, curMax);//记录最大值
        per = curMax;//记录当前节元素为尾的最大子数组和
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14