题目链接

LeetCode

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

输入： nums = [-100000]
输出： -100000

提示：

  • 1 <= nums.length <= 3 * 104
  • -105 <= nums[i] <= 105

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

解题思路

方法一：动态规划

image.png

  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         int pre = 0,ans = nums[0];
  5.         int pos = 0;
  6.         for(const int n:nums){
  7.             pre = max(pre+n,n);
  8.             ans = max(pre,ans);
  9.         }
  10.         return ans;
  11.     }
  12. };

要求输出子数组：

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0){
            return -1;
        }
        int res = nums[0];
        int dp = res;
        // 记录最大子数组的右边界
        int pos = 0;
        for(int i = 1; i < nums.length; ++i){
            dp = Math.max(dp + nums[i], nums[i]);
            // 记录最大子数组的右边界
            if(dp > res){
                res = dp;
                pos = i;
            }
        }
        // 查找左边界
        int left = right;
        while(left >= 0 && dp[left] >= 0){
            --left;
        }
        //输出最大子数组
        for(int i = left + 1; i <= right; ++i){
            System.out.println(nums[i]);
        }
        return res;
    }
}
  • 时间复杂度 O(n)
  • 空间复杂度 O(1)