LeetCode—53. 最大子数组和（中等）

目录

题目描述：

思路一：动态规划

实现代码：

思路二：贪心算法

实现代码：

仅供个人学习使用

题目描述：

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

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

示例 1：

示例2：

示例3：

思路一：动态规划

如果前一个元素大于0，则加到当前元素上。对于这个问题，我们可以采用以下步骤：

        1. 定义状态：

         令dp[i]表示以nums[i]结尾的最大子数组和。

        2. 状态转移方程：

        对于每个i（从1到n-1），dp[i]可以由dp[i-1] + nums[i]得到，如果dp[i-1]是正数，因为加上前面的子数组和会更大。

        如果dp[i-1]是负数，那么dp[i]应该直接等于nums[i]，因为加上一个负数的和会减少总和，不如从当前元素开始新的子数组。

        3. 初始化和遍历：

        初始化dp[0] = nums[0]，因为以第一个元素结尾的子数组和就是它本身。

        遍历数组，对于每个元素nums[i]，根据状态转移方程更新dp[i]。

        4. 记录最大值：

        在遍历的过程中，同时记录下所有dp[i]中的最大值，这个值就是整个数组中的最大子数组和。

        5. 优化空间：

• 由于我们只关心以每个元素结尾的最大子数组和，而不是整个数组的子数组和，所以我们可以只使用一个变量pre来存储dp[i]的值，而不需要一个数组。
• 同时，我们使用另一个变量maxAns来记录遍历过程中遇到的最大和。

这种方法的核心思想是，对于每个元素，我们考虑两种情况：要么我们将其与前一个元素组合，要么我们不组合。我们总是选择给我们最大和的选项。这样，当我们到达数组的末尾时，我们已经找到了具有最大和的子数组。

实现代码：

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0,maxAns = nums[0];
        for(int x:nums){
            pre = Math.max(x,pre+x);
            maxAns = Math.max(pre,maxAns);
        }
        return maxAns;
    }
}

思路二：贪心算法

若当前指针所指向的元素之前的和小于0，则丢弃当前元素之前的数列。

实现代码：

class Solution {
    public int maxSubArray(int[] nums) {
        int sum=0,maxAns=nums[0];
        for(int x:nums){
            sum+=x;
            if(sum>maxAns) maxAns=sum;
            if(sum<0) sum=0;
        }
        return maxAns;
    }
}