250x250
반응형
Notice
Recent Posts
Recent Comments
Link
N
(Leet Code c++)Maximum Subarray 본문
728x90
반응형
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23
Constraints:
- 1 <= nums.length <= 3 * 104
- -105 <= nums[i] <= 105
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
for(int i = 1; i < nums.size(); i++){
nums[i] = max(nums[i], nums[i] + nums[i - 1]);
}
return *max_element(nums.begin(), nums.end());
}
};
728x90
반응형
'Leet Code 알고리즘' 카테고리의 다른 글
(Leet Code c++)Length of Last Word (0) | 2021.07.09 |
---|---|
(Leet Code c++)Container With Most Water (0) | 2021.07.08 |
(Leet Code c++)Search Insert Position (0) | 2021.07.07 |
(Leet Code c++)Implement strStr() (0) | 2021.07.07 |
(Leet Code c++)Remove Element (0) | 2021.07.07 |