Problem:
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
.
Idea:
DP
Solution:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Runtime: 6 ms (better than 98.66%) class Solution { public: int maxSubArray(vector<int>& nums) { vector<int> f(nums.size()); f[0] = nums[0]; for (int i = 1; i < nums.size(); ++i) f[i] = max(f[i - 1] + nums[i], nums[i]); return *std::max_element(f.begin(), f.end()); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment