0053.Maximum-Subarray

最大子数组和

1. 题目

1.1. 描述

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

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

1.2. 示例

示例 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.3. 提示

• 1 <= nums.length <= $10^5$
• -$10^4$ <= nums[i] <= $10^4$

1.4. 进阶

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

2. 思路

2.1. 卡丹算法

维基百科

• 定义的ans变量返回最终值，tempSum变量得到以该位置为结束的最大子数列和该位置数值的更大值
• 时间复杂度为O(n)，空间复杂度为O(1)

2.2. 分治法

• 数组一分为二，寻找左右两边的最大子数组和，层层二分，找到左/中/右的最大值
• 时间复杂度为O(nlogn)，空间复杂度为O(logn)

3. 代码

3.1. C++

3.1.1. 卡丹算法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int len = nums.size();
        int tempSum = 0;
        for (int i = 0; i < len; i++)
        {
            tempSum = max(tempSum+nums[i],nums[i]);
            ans = max(tempSum,ans);
        }
        return ans;

    }
};

3.1.2. 分治法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return dfs(nums,0,nums.size()-1);
    }
    int dfs(vector<int>& nums,int left,int right){
        if(left>=right) return nums[left];
        int leftSum = 0, rightSum = 0;
        int mid = left+(right-left)/2;
        for (int i = mid-1,tempSum = 0;i>=left;i--)
        {
            tempSum+=nums[i];
            leftSum=max(leftSum,tempSum);
        }
        for (int i = mid+1,tempSum = 0;i<=right;i++)
        {
            tempSum+=nums[i];
            rightSum=max(rightSum,tempSum);
        }
        return max({dfs(nums,left,mid-1),dfs(nums,mid+1,right),leftSum+nums[mid]+rightSum});
    }
};

3.2. Java

3.2.1. 卡丹算法

class Solution {
    public int maxSubArray(int[] nums) {
        int tempSum = 0;
        int ans = nums[0];
        for (int num : nums) {
            tempSum = Math.max(tempSum+num, num);
            ans = Math.max(tempSum,ans);
        }
        return ans;
    }
}

3.2.2. 分治法

class Solution {
    public int maxSubArray(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    private int dfs(int[] nums,int left,int right){
        if(left>=right) return nums[left];
        int leftSum = 0,rightSum = 0;
        int mid = left+(right-left)/2;
        for (int i = mid-1,tempSum = 0; i >=left; i--) {
            tempSum+=nums[i];
            leftSum=Math.max(leftSum, tempSum);
        }
        for (int i = mid+1,tempSum=0; i <= right; i++) {
            tempSum+=nums[i];
            rightSum=Math.max(rightSum, tempSum);
        }
        return Math.max(Math.max(dfs(nums,left,mid-1),dfs(nums,mid+1,right)),leftSum+nums[mid]+rightSum);
    }
}