【算法与数据结构】53、LeetCode最大子数组和

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：程序一共两个变量，一个result一个count。result用来记录最终的结果，count记录当前的子序列和。如果说当前和（count）大于上次的最大和（result），就更新result。每当当前和小于0是就将count重置为0，因为小于0的和不会增加count的值可以直接舍去。例如，[-2,1,-3,4,-1,2,1,-5,4]，-2+1=-1。那么最大和的连续子数组可以从1开始计算，-2直接不用。
  程序如下：

class Solution {
   
public:
	int maxSubArray(vector<int>& nums) {
   
		int result = INT32_MIN;		// 32位最小值
		int count = 0;
		for (int i = 0; i < nums.size(); i++) {
   
			count = count + nums[i];
			if (count > result) result = count;
			if (count < 0) count = 0;
		}
		return result;
	}
};

复杂度分析：

• 时间复杂度： $O(n)$。
• 空间复杂度：$O(1)$。

三、完整代码

# include <iostream>
# include <vector>
using namespace std;

class Solution {
   
public:
	int maxSubArray(vector<int>& nums) {
   
		int result = INT32_MIN;		// 32位最小值
		int count = 0;
		for (int i = 0; i < nums.size(); i++) {
   
			count = count + nums[i];
			if (count > result) result = count;
			if (count < 0) count = 0;
		}
		return result;
	}
};
int main() {
   
	vector<int> nums = {
    -2,1,-3,4,-1,2,1,-5,4 };
	Solution s1;
	int result = s1.maxSubArray(nums);
	cout << result << endl;
	system("pause");
	return 0;
}

end