leetcode - 53. Maximum Subarray - Easy

descrition

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解析

这是算法导论上的经典例题，用于介绍“分而治之”思想的。

这里可以达到的最优解是: 时间-O(n)，空间-O(1)。核心思想是动态规划，使用 dp[i] 表示截止 nums[i] 的连续最大和，dp[i] = max( dp[i-1] + nums[i], nums[i] )，而最大和就是 dp[0,...,n-1] 中的最大值。基于观察发现 dp[i] 的计算只依赖于前一步的结果，因此可以进一步减小空间复杂度，迭代时的状态变换：curSum = max(curSum+nums[i], nums[i])，同时用 maxSum 存储当前的最大值，即 maxSum = max(maxSum, curSum)。

具体实现参考代码。对“分而治之”思想感兴趣的可以参考「算法导论」。

code

#include <iostream>

#include <vector>

#include <algorithm>

#include <limits>

using namespace std;

class Solution{

public:

	int maxSubArray(vector<int>& nums){

		int curSum = 0;

		int maxSum = numeric_limits<int>::min();

		for(int n : nums){

			if(curSum < 0){

				curSum = n;

			}else{

				curSum += n;

			}

			maxSum = max(maxSum, curSum);

		}

		return maxSum;

	}

};

int main()

{

	return 0;

}