LeetCode 53/152 Maximum Subarray/Maximum Product Subarray---DP **

╰+哭是因爲堅強的太久メ 2022-08-07 12:43 16阅读 0赞

一：[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`.

链接：https://leetcode.com/problems/maximum-subarray/

分析：这题就是求最大连续字串的和，或者说是求和最大的连续子数组

此题最简单的是暴力，但是暴力为O(N^2)， 超时。另外可以采用动态规划来求解，关键是如何转换为动态规划问题，即如何表述成动态规划问题。

我们用local\[i\]来表示以A\[i\]结尾的连续子数组的最大和，那么local\[0\] = A\[0\],, local\[1\]等于要么local\[0\]+A\[1\] 要么就等于A\[1\]本身，关键看两者谁更大，于是便得到递归式local\[i+1\] = max(local\[i\]+A\[i\], A\[i\]),,,,local数组中的最大值即为所求。 迭代的过程中无需数组 因此时间复杂度为O(N), 空间复杂度为O(1).

class Solution {
    public:
        int maxSubArray(int A[], int n) {
            if(n == 0) return 0;
            int sum = A[0];         // 以A[0]结束的连续子数组和最大值
            int maxResult = A[0];
            for(int i = 1; i < n; i++){
                sum = max(A[i],A[i]+sum);      // 以A[i]结束的连续子数组和最大值
                if(maxResult < sum) maxResult = sum; 
            }
            return maxResult;
        }
    
    };

二：[Maximum Product Subarray][]

题目：

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array `[2,3,-2,4]`,  
the contiguous subarray `[2,3]` has the largest product = `6`.

链接：https://leetcode.com/problems/maximum-product-subarray/

分析：此题我们不仅要保存一个最大值，还得保存一个最小值，因为负负相乘等于正数，比如-2 4 -5，即localMIn\[i\]表示以i结尾的连续字串乘积的最小值，而localMax\[i\]表示以i结尾的连续字串乘积的最大值，那么localMax\[i\] = max(max(localMin\[i\]\*A\[i\], A\[i\]\*localMax\[i\]), A\[i\]); 而localMin\[i\]=min(min(localMin\[i\]\*A\[i\], A\[i\]\*localMax\[i\]), A\[i\]);

class Solution {
    public:
        int maxProduct(int A[], int n) {
            if(n == 0) return 0;
            int result = A[0];
            int minProduct = A[0];
            int maxProduct = A[0];
            for(int i = 1; i < n; i++){
                int temp = max(A[i]*maxProduct, A[i]*minProduct);
                temp = max(temp, A[i]);
                minProduct = min(A[i]*maxProduct, A[i]*minProduct);
                minProduct = min(minProduct, A[i]);
                maxProduct = temp;
                result = max(maxProduct, result);
            }
            return result;
            
        }
    };

[Maximum Subarray]: https://leetcode.com/problems/maximum-subarray/
[Maximum Product Subarray]: https://leetcode.com/problems/maximum-product-subarray/