53. 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.
题解:
输入一个数组,求数组的连续子数组中,最大的一段的和;
原问题:n个数的数组(nums)的最大子段和;
子问题:
一个数的数组的最大子段和:dp[0] = nums[0];
两个数的数组的最大子段和:两种情况,加上第一个数(dp[0] + nums[1])或不加上第一个数(nums[1]):dp[1] = max(dp[0] + nums[1], nums[1]);其实也就相当于是以第二个数作为子段结尾的情况下的最优解;然后再取max(dp[0], dp[1]);
确认状态:
n个数的数组的最大子段和:
以nums[n-1]结尾的最大子段和前n-1个子段最大和比较,取最大值;
动态规划状态转移方程:
以第n个数结尾的最大子段和:dp[n-1] = (dp[n-2] + nums[n-1], nums[n-1])
边界状态:dp[0] = nums[0];
最后输出:max(dp[0],dp[1],.....dp[n-1])
My Solution(C/C++)
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxSubArray(vector<int> &nums) {
vector<int> dp(nums.size() + 3, 0);
if (nums.size() == 0) {
return 0;
}
dp[0] = nums[0];
int max_dp = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
if (max_dp < dp[i]) {
max_dp = dp[i];
}
}
return max_dp;
}
};
int main() {
vector<int> nums;
nums.push_back(-2);
nums.push_back(1);
nums.push_back(-3);
nums.push_back(4);
nums.push_back(-1);
nums.push_back(2);
nums.push_back(1);
nums.push_back(-5);
nums.push_back(4);
Solution s;
printf("最大子段和:%d", s.maxSubArray(nums));
return 0;
}
结果
最大子段和:6
My Solution 1(Python)
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
sum, result = 0, 0
for i in range(len(nums)):
sum += nums[i]
if sum < 0:
sum = 0
else:
result = max(sum, result)
if result == 0:
return max(nums)
return result
My Solution 2(Python)
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = []
if len(nums) == 0:
return []
dp.append(nums[0])
max_dp = dp[-1]
for i in range(1, len(nums)):
dp.append(max(dp[i-1] + nums[i], nums[i]))
if max_dp < dp[-1]:
max_dp = dp[-1]
return max_dp
Reference (转)
Python:
class Solution(object):
def maxSubArray(self, nums):
for i in xrange(1,len(nums)):nums[i]=max(nums[i], nums[i]+nums[i-1])
return max(nums)
Java:
class Solution {
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
}
网友评论