Algo: maxSubArray vs. maxProduct

这两个问题类似，都可利用动态规划思想求解。

一、最大连续子序列和

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 ;

    }

    int currMax = nums[];

    int maxResult = nums[];

    int size = (int)nums.size();

    for (int i = ; i < size; ++i)

    {

        currMax = std::max(nums[i], currMax + nums[i]);

        maxResult = std::max(maxResult, currMax);

    }

    return maxResult;

}

二、最大连续子序列积

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 ;

    }

    int size = (int)nums.size();

    int currMax = nums[];

    int currMin = nums[];

    int maxResult = nums[];

    for (int i = ; 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;

}

巴特西

Algo: maxSubArray vs. maxProduct

最新文章

热门文章