【LeetCode 每日一题】53. 最大子数组和

01 题目描述

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

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

02 示例

 示例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 <= 10^5
• -10^4 <= nums[i] <= 10^4

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

03 C++代码

 方法一：动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 动态规划思路
        int pre = 0, max_Ans = nums[0];
        // 其中pre这个变量用来维护对于当前f(i)的f(i-1)的值是多少，最终的空间复杂度降到了O(1).
        for (const auto x: nums){
            pre = max (pre + x, x);
            max_Ans = max(max_Ans, pre);
        }
        return max_Ans;
    }
};

复杂度分析：

• 时间复杂度：O(N)，其中N是nums数组的长度。我们只需要遍历一遍数组即可求得答案。
• 空间复杂度：O(1)。 

方法二：分治法  五大常用算法之一：分治算法 - 红脸书生 - 博客园

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

class Solution {
public:
    struct Status{
        int lSum, rSum, mSum, iSum;
    };
 
    Status pushUp(Status l, Status r){
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };
 
    Status get(vector<int> &a, int l, int r) {
        if(l == r){
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }
 
    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

复杂度分析：

假设序列a的长度为n。

• 时间复杂度：假设我们把递归的过程看作是一颗二叉树的先序遍历，那么这颗二叉树的深度的渐进上界为O(logn)，这里的总时间相当于遍历这颗二叉树的所有节点，故总时间的渐进上界是，故渐进时间复杂度为O(n)。
• 空间复杂度：递归会使用O(logn)的栈空间，故渐进空间复杂度为O(logn)。

04 一点感想

        真的难吗（我也不知道），加油鸭

05 刷题进度

 

学习目标：坚持刷题 坚持刷题 坚持刷题！！！ 

那写看似毫无波澜的日复一日，会在某一天 让你突然发现努力的意义。
无悔昨天 & 感谢今天 & 喜欢明天~

 一以贯之的努力，不得懈怠的人生。每天的微小积累，会决定最终的结果，这 就是答案！