[数据结构与算法]LeetCode 53. 最大子数组和（最大子序和）——每日一练第6天（Java语言）

题目来源：最大子数组和——每日一练第6天（Java语言）
同时也是：LeetCode 53. 最大子数组和（最大子序和）

题目详情

给你一个整数数组 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 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

（一）暴力解法

排列所有的连续子数组，求出和，在所有的和中挨个比较，找到其最大的和。以nums = [5,4,-1,7,8]为例

从上方表格中，可以显而易见，最大的连续子数组和为23。

（二）动态规划

我们在遍历数组的同时，去计算以nums[i]结尾的最大子序和，以nums = [5,4,-1,7,8]为例，用dp[i]表示nums中以nums[i]结尾的最大子序和。遍历数组：

最后我们只需要在数组dp中，找到最大值，即为最大的子序和。

（三）贪心算法

遍历数组时，把每一位数字加起来，计算其和记为sum，并比较出最大值max

• 如果sum<=0，说明保留这些数字，只会有负增益，所以需要舍弃之前的数字，重新开始计算，sum = nums[i]
• 如果sum>0，说明保留这些数字，可以带来增益，所以保留这些数字，sum += nums[i]
  需要注意的是：如果数组中的所有数字都为负数的话，此时无论增加什么数字，只会带来负增益，所以此时的最大子数组和，就是这些负数中最大的那个负数。

代码实现

（一）暴力解法

时间复杂度为O(n²)，遇到数据量大的，很有可能会超时

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i < nums.length ; i++) {
            int sum = 0;
            for(int j = i ; j < nums.length ; j++) {
                sum +=nums[j];
                if(sum >= max) {
                    max = sum;
                }
            }
        }
        return max;
    }
}

（二）动态规划

时间复杂度为O(n)

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        int max = dp[0];
        // [1,len-1]遍历数组
        for(int i = 1 ; i < len ; i++) {    
            int temp = dp[i-1] + nums[i];
            if(temp < nums[i] ) {
                dp[i] = nums[i];
            } else {
                dp[i] = temp;
            }
            // 在数组dp中，找最大值
            if(dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }
}

（三）贪心算法

时间复杂度为：O(n)

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        // 遍历数组，找出最大值
        int max_nums = Integer.MIN_VALUE;
        for(int i = 0 ; i < nums.length ; i++) {
            if(max_nums < nums[i]) {
                max_nums = nums[i];
            }
        }
        if(max_nums <= 0) {     // 特殊情况：nums中的又负数和0组成
            return max_nums;
        }
        int sum = 0;
        int max = nums[0];
        for(int i = 0 ; i < nums.length ; i++) {
            if(sum > 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
            max = Math.max(max,sum);
        }
        return max;
    }
}