Open guodongxiaren opened 4 years ago
经典DP题: dp[i] 表示从左向右看,以i结尾的最大子数组和。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int size = nums.size();
if (size == 0) {
return 0;
} else if (size == 1) { // 这个else if也可以去掉,加上会加快一点点速度
return nums[0];
}
int* dp = new int[size];
memset(dp, 0, sizeof(int)*size);
dp[0] = nums[0];
int max_sum = nums[0];
for (int i = 1; i < size; ++i) {
dp[i] = max(nums[i], dp[i-1]+nums[i]);
max_sum = max(max_sum, dp[i]);
}
return max_sum;
}
};
对于DP解法,也可以不新建dp数组,直接复用原数组(如果面试官优化的话)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int size = nums.size();
if (size == 0) {
return 0;
} else if (size == 1) {
return nums[0];
}
int max_sum = nums[0];
for (int i = 1; i < size; ++i) {
nums[i] = max(nums[i], nums[i-1]+nums[i]);
max_sum = max(max_sum, nums[i]);
}
return max_sum;
}
};
https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。