首页 > 代码库 > LeetCode53 Maximum Subarray

LeetCode53 Maximum Subarray

题目:

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. (Medium)

分析:

遍历一遍,维护一个当前最大值temp,如果temp < 0,则temp = nums[i](前面的元素和更小,不要加进去), 否则 temp += nums[i];

然后每个temp更新result.

代码:

 1 class Solution { 2 public: 3     int maxSubArray(vector<int>& nums) { 4         if (nums.size() == 0) { 5             return -1; 6         } 7         int temp = nums[0], result = nums[0]; 8         for (int i = 1; i < nums.size(); ++i) { 9             if (temp < 0) {10                 temp = nums[i];11                 result = max(temp, result);12             }13             else {14                 temp = nums[i] + temp;15                 result = max(temp, result);16             }17         }18         return result;19     }20 };

题目还有分治和动归的算法,明天再说...

 

LeetCode53 Maximum Subarray