leetcode-53 Maximum Subarray

53. Maximum Subarray

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the $O(n)$ solution, try coding another solution using the divide and conquer approach, which is more subtle.

Analyse

找出一个数组连续子序列的最大和

子序列要求连续，子序列向右扩展分为两种情况

  1. 将新元素加入子序列，子序列长度+1
  2. 抛弃之前的子序列，新元素成为新的子序列，子序列长度为1

子序列的局部最大和为这两种情况中和最大的那个

在所有的局部最大和中找出全局最大和

写出一个算法复杂度为$O(n)$的版本

1
2
3
4
5
6
7
8
9
10
int maxSubArray(vector<int>& nums)
{
    int max = nums[0], global_max = nums[0];
    int len = nums.size();
    for (int i = 1; i < len; i++) {
        max = max > 0 ? nums[i] + max : nums[i];
        global_max = max > global_max ? max : global_max;
    }
    return global_max;
}