最大子数组和java实现【动态规划基础练习】

12.15 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

解题思路： 点击详解

1.定义状态（定义子问题）：dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。

2.状态转移方程（描述子问题之间的联系）：如果 dp[i - 1] > 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面，得到和更大的连续子数组；如果dp[i - 1] < 0，那么 nums[i]加上前面的数 dp[i - 1] 以后值不会变大。此时单独的一个 nums[i] 的值，就是 dp[i]

//法一
class Solution {
   public static int maxSubArray(int[] nums) {
        int n =  nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int num = dp[0];
        for(int i = 1;i < n;i++){
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + nums[i];
            }else{
                dp[i] = nums[i];   
            }
            num = Math.max(dp[i],num);
        }
        return num;
   }
}

空间优化后的代码

//法二
class Solution {
   public static int maxSubArray(int[] nums) {
        int n =  nums.length;
        int num = nums[0];
        for(int i = 1;i < n;i++){
            if(nums[i-1] > 0){
                nums[i] = nums[i-1] + nums[i];
            }else{
                nums[i] = nums[i];   
            }
            num = Math.max(nums[i],num);
        }
        return num;
   }
}