LeetCode 0053 - Maximum Subarray
# Hints
- DP
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Easy |
Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the solution, try coding another solution using the divide and conquer approach, which is more subtle.
# 题意
给定一个整数数组 nums
,求其最大非空连续子序列和。
# 题解
最大连续子序列和是经典的动态规划入门问题。
亦可用分治法求解,但代码要复杂得多,没有必要。
# AC代码
class Solution {
public:
int maxSubArray(vector<int> & nums) {
// 初始化
int n = nums.size();
int res = nums[0];
// 求解
int sum = nums[0];
for (int i = 1; i < nums.size(); i ++) {
// 递推
if (sum < 0) {
sum = nums[i];
} else {
sum += nums[i];
}
// 更新答案
res = max(res, sum);
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01