要求时间复杂度 O(n)。
e.g. 给定数组 [-2,1,-3,4,-1,2,1,-5,4],其中有连续子序列 [4,-1,2,1] 和最大为 6。
我完全没有想法,看了答案。
C++实现:
1 int maxSubArray(vector<int>& nums) { 2 int result = nums[0], sum = 0; 3 for (int i = 0; i < nums.size(); i++) { 4 sum = max(sum, 0); 5 sum += nums[i]; 6 result = max(sum, result); 7 } 8 return result; 9 }
或者
1 int maxSubArray(vector<int>& nums) { 2 int result = nums[0], sum = 0; 3 for (int i = 0; i < nums.size(); i++) { 4 sum = max(sum + nums[i], nums[i]); 5 result = max(sum, result); 6 } 7 return result; 8 }