這兩個問題類似颂碧，都可利用動態(tài)規(guī)劃思想求解墩瞳。
一查吊、最大連續(xù)子序列和
https://leetcode.com/problems/maximum-subarray/description/
https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
The core ideas are the same:
currentMax = max(nums[i], some_operation(currentMax, nums[i])).
For each element, we have 2 options: put it inside a consecutive subarray, or start a new subarray with it.
#include <vector>
int maxSubArray(std::vector<int>& nums)
{
if (nums.empty())
{
return 0;
}
int currMax = nums[0]; int maxResult = nums[0]; int size = (int)nums.size(); for (int i = 1; i < size; ++i)
{
currMax = std::max(nums[i], currMax + nums[i]);
maxResult = std::max(maxResult, currMax);
}
return maxResult;
}
二通惫、最大連續(xù)子序列積
https://stackoverflow.com/questions/25590930/maximum-product-subarray
https://leetcode.com/problems/maximum-product-subarray/description/
https://www.geeksforgeeks.org/maximum-product-subarray/
https://www.geeksforgeeks.org/maximum-product-subarray-added-negative-product-case/
https://www.geeksforgeeks.org/maximum-product-subarray-set-2-using-two-traversals/
#include <vector>
int maxProduct(std::vector<int>& nums)
{
if (nums.empty())
{
return 0;
}
int size = (int)nums.size();
int currMax = nums[0];
int currMin = nums[0];
int maxResult = nums[0];
for (int i = 1; i < size; ++i)
{
int t_currMax = currMax * nums[i];
int t_currMin = currMin * nums[i];
currMax = max(nums[i], max(t_currMax, t_currMin));
currMin = min(nums[i], min(t_currMax, t_currMin));
maxResult = max(maxResult, currMax);
}
return maxResult;
}
