LeetCode热题100：动态规划

摘要

题目	知识点
53. 最大子数组和 - 力扣（LeetCode）	线性DP

最大子数组和

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

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

class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		int dp = 0; // dp: 到上一个位置为止的最长连续和
		int ans = INT_MIN;
		for(int i = 0 ; i < nums.size() ; i ++){
			ans = max(ans, nums[i] + dp);
			dp += nums[i];
			if(dp < 0) dp = 0;
		}
		return ans;
	}
};