面试题 16.17. 连续数列

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

输入： [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。

分治算法：

class Solution { public: int maxSubArray(vector<int>& nums) { int size = nums.size(); if (size == 1) { return nums[0]; } vector<int> left(nums.begin(), nums.begin() + size / 2); vector<int> right(nums.begin() + size / 2, nums.end()); int leftMaxNumber = maxSubArray(left), rightMaxNumber = maxSubArray(right); int middleMaxNumber = 0, middleLeft = 0, middleRight = 0, temp = -10001; for (int i = size / 2 - 1; i >= 0 ; --i) { middleLeft += nums[i]; if (temp < middleLeft) { temp = middleLeft; } } middleMaxNumber += temp; temp = -10001; for (int j = size / 2; j < size; ++j) { middleRight += nums[j]; if (temp < middleRight) { temp = middleRight; } } middleMaxNumber += temp; return max(middleMaxNumber, max(leftMaxNumber, rightMaxNumber)); } };

动态规划：

class Solution { public: int maxSubArray(vector<int>& nums) { int count = 0, maxCount = INT32_MIN; for (auto& i : nums) { count = max(count + i, i); maxCount = max(count, maxCount); } return maxCount; } };

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/contiguous-sequence-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。