leetcode 53. Maximum Subarray 、152. Maximum Product Subarray

53. Maximum Subarray

之前的值小于0就不加了。dp[i]表示以i结尾当前的最大和，所以需要用一个变量保存最大值。

动态规划的方法：

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        vector<int> dp(nums.size());

        int res = INT_MIN;

        for(int i = ;i < nums.size();i++){

            dp[i] = nums[i];

            if(i >  && dp[i-] >= )

                dp[i] += dp[i-];

            res = max(res,dp[i]);

        }

        return res;

    }

};

152. Maximum Product Subarray

最小值可能是负数，这个值可能变成最大值。

dp[i]表示以i结尾当前的最大乘积，所以需要用一个变量保存最大值。

为什么每次要与nums[i]做对比，因为数组中可能存在0

动态规划的方法：

class Solution {

public:

    int maxProduct(vector<int>& nums) {

        vector<int> dp_max(nums.size());

        vector<int> dp_min(nums.size());

        dp_max[] = nums[];

        dp_min[] = nums[];

        int res = nums[];

        for(int i = ;i < nums.size();i++){

            dp_max[i] = max(dp_max[i-] * nums[i],max(dp_min[i-] * nums[i],nums[i]));

            dp_min[i] = min(dp_max[i-] * nums[i],min(dp_min[i-] * nums[i],nums[i]));

            res = max(res,dp_max[i]);

        }

        return res;

    }

};

非动态规划，节省空间的方法：

https://blog.csdn.net/whuwangyi/article/details/39577455解法3

class Solution {

public:

    int maxProduct(vector<int>& nums) {

        int max = nums[];

        int pre_max = nums[],pre_min = nums[];

        int cur_max,cur_min;

        for(int i = ;i < nums.size();i++){

            cur_max = compare_max(pre_max*nums[i],pre_min*nums[i],nums[i]);

            cur_min = compare_min(pre_max*nums[i],pre_min*nums[i],nums[i]);

            pre_max = cur_max;

            pre_min = cur_min;

            max = cur_max > max ? cur_max : max;

        }

        return max;

    }

    int compare_max(int a,int b,int c){

        int max = a;

        if(b > max)

            max = b;

        if(c > max)

            max = c;

        return max;

    }

    int compare_min(int a,int b,int c){

        int min = a;

        if(b < min)

            min = b;

        if(c < min)

            min = c;

        return min;

    }

};

巴特西

leetcode 53. Maximum Subarray 、152. Maximum Product Subarray

最新文章

热门文章