每天一道LeetCode-----找到给定数组的连续子数组，使这个子数组的和最大，要求复杂度为O(n)

Maximum Subarray

原题链接Maximum Subarray

在给定数组中找到一个子数组（连续），使这个子数组的和最大。

O(n2)的解法是求sum[i] - sum[j]的最大值，形如sum[i]的式子表示数组[0 : i)的和。这种方法需要i和j都从[0:n)遍历一遍，复杂度比较高。

假设当前找到一个范围[left, right]，考虑以下两种情况

• 存在某个[i, left)范围的和大于0，那么[i, right]的和一定大于[left, right]的和
• 存在某个[j, left)范围的和小于0，那么[j, right]的和一定小于[left, right]的和

不过，运算过程中不是先找[left, right]再找i，而是先找[i, left)，同时假设[left, right]已存在。也就是说有两种情况

• 如果当前范围的和大于0，那么如果这个范围作为结果范围的一部分，可知会增加结果的大小。是上述第一种情况，继续添加后面的元素即可
• 如果当前范围的和小于0，那么如果这个范围作为结果范围的一部分，可知会减小结果的大小。是上述第二中情况，就需要把当前范围抛弃，从下一位开始重新计算和

当然，在上述遍历的过程中，需要不断判断当前遍历到的子数组的和，更新最大值。

考虑以下问题

• 找到范围[i, left)，且范围和为sum1。此时存在i < j < left使[j, left)范围的和sum2 > sum1，那么结果会不会是[j, right]而非[i, right]呢？
  
  • 不会，因为在找[i, left)的过程中是时刻保持[i, left)的和大于0的，当然[i, j)范围的和也会大于0，那么将[i, j)范围添加到结果范围中，是会增加结果的值，所以结果范围仍然是[i, right]
• 找到范围[i, left)，且范围和为sum1。此时存在i < j < left使[i, j)范围的和小于0，那么需不需要将[i, j)范围去掉
  
  • 不需要，因为根本不存在这样的j使[i, j)范围的和小于0，原因如第一个问题

代码如下

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty())
            return 0;

        /* sum是当前范围的和，即[i, left)范围的和 */
        int sum = 0;
        /* ans是找到的最大的和 */
        int ans = nums[0];
        for(int i = 0; i < nums.size(); ++i)
        {
            /* 此时sum是大于等于0的，然后将下一个元素添加进范围 */
            sum += nums[i];
            /* 更新最大值 */
            ans = std::max(ans, sum);
            /* 如果当前范围和(sum)大于0，继续添加下一个，否则，重置为0 */
            sum = std::max(sum, 0);
        }
        return ans;
    }
};

---

由于本题要求是O(n)的复杂度，所以只能进行单层for循环，也就是说只能从下标0开始运算，那么每遍历到一个位置都必须考虑以下两个问题

• 是否应该丢弃当前范围的左边界
• 是否应该添加当前遍历到的这个元素

又因为数组元素比较多，每个元素都考虑这两种情况会使复杂度飙升。

本题的解决思路是

• 如果当前找到的范围[i, left)的和是大于0的，那么根本不需要丢弃当前范围的左边界，直接添加遍历到的新元素
• 如果当前找到的范围[i, left)的和是小于0的，那么抛弃已找到的范围，从遍历到的新元素开始重新寻找范围