算法设计与分析[0009] Dynamic Programming(II)（Maximum Sum/Product Subarray）

编程珠玑Algorithm

　本文通过 53. Maximum Subarray & 152. Maximum Product Subarray 分析根据动态规划思路进行问题求解中的一个关键环节：子问题的拆分和求解。

Problem Description

  • 两道题解决的问题相似，都是求解给定序列中满足某种数学特征（和最大/乘积最大）的子序列，虽然不需要将该子序列输出。

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

  • 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.
  • For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
  • 留意的关键字眼是：containing at least one number，所以给定序列至少有一个元素，这也启发我们可以将其作为特殊处理。

53. Maximum Subarray 解题思路

  • 思路一：$sums[j]$ 为序列前 j 个元素的最大子段和作为求解的子问题，则 $sum[n]$ 则为问题的答案。然而，如何利用 $sums[1, 2, …, j-1]$ 对 $sums[j]$ 进行求解呢？显然需要知道前 j 个元素的最大字段和的子段起始和终止位置，求解这个子问题的状态迁移显然比较复杂。
  • 换一种思路。思路二：$sums[j]$ 为以第 j 个元素为结尾的子段的最大子段和作为求解的子问题，$max_{1 \leq j \leq n}(sums[j])$ 即为整个序列的最大子段和。而通过 $sums[j-1]$ 和当前元素 $nums[j]$ 即可计算以第 j 个元素为结尾的最大子段和 $sums[j]$，状态转移方程 如下：
    $$ sums[j+1] = \begin{cases} nums[j+1]　　　　　　sums[j] \lt 0 \cr sums[j] + nums[j+1]　others \end{cases}$$
  • 根据思路二，53. Maximum Subarray 解答如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int SizeofNums = nums.size();
        if(SizeofNums == 1) {
            return nums[0];
        }
        int sums[SizeofNums];
        sums[0] = nums[0];
        for(int i=1; i<SizeofNums; i++) {
            // sums[i]: The largest sum of subarray ending with the i-th element
            sums[i] = sums[i-1]<0 ? nums[i] : sums[i-1]+nums[i]; 
        }
        
        // The largest sum of the whole array
        int largestSum = sums[0];
        for(int i=1; i<SizeofNums; i++) {
            if(largestSum < sums[i]) {
                largestSum = sums[i];
            }
        }
        
        return largestSum;
    }
};
  • 为了得到 largestSum 对应的子序列，我们可以通过变量 startIdx 记录以第 j 个元素结尾（endIdx）的最大子段和对应子序列的起始位置，$nums[startIdx, …, endIdx]$ 即为对应的子序列；另外，考虑到当前状态只与前一个状态有关，所以可以使用变量代替数组，节省内存，同时，避免获取The largest sum of the whole array 时的重复循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int SizeofNums = nums.size();
        if(SizeofNums == 1) {
            return nums[0];
        }
        // largest sum for the subarray ending with current element 
        int curSum = nums[0];
        // largest sum of subarray for the whole array
        int largestSum = curSum;
        // subarray[startIdx, endIdx] with largest sum for the whole array
        int startIdx = 0, endIdx = 0;
        for(int i=1; i<SizeofNums; i++) {
            if(curSum < 0) {
                curSum = nums[i];
                startIdx = i;
            }
            else {
                curSum = curSum + nums[i];
            }
            
            if(curSum > largestSum) {
                largestSum = curSum;
                endIdx = i;
            }
        }
        
        return largestSum;
    }
};

152. Maximum Product Subarray 解题思路

  • 这一题的解题流程与上一题基本类似，但是要解决的关键问题是：状态转移，即如何根据上一个子问题（以第 j 个元素为结尾的子段的max product）的答案推算出当前子问题的结果。
  • 从上一题的分析可以看出，当前子问题（以第 j 个元素为结尾的子段的max sum）的计算只需考虑上一个子问题的结果 $sum[j-1]$，$sum[j-1] < 0$，因为是加法，显然可以将子问题结果忽略；$sum[j-1] > 0$，$sum[j-1]$ 加上当前元素就是当前子问题的结果。
  • 类似的问题，只不过换成乘积，子问题的求解就变得复杂了，需要考虑以下几种情况：
    • 当前元素是正数，max product可能是正正得正的情况，因为都是整数，乘积＞1，上一子问题的结果乘上当前元素即为当前子问题的答案
    • 当前元素是负数，max product可能是负负得正的情况，因此需要维护以第 j 个元素为结尾的子段的min product（很大可能是负数）
    • 另外，需要考虑上一个子问题的结果为0的情况
    • 总之，乘积的最大值为上述三种情况之一
      状态转移方程如下：
      $$ maxProducts[j+1] = max(maxProducts[j-1]*nums[j], minProducts[j-1]*nums[j], nums[j])$$
  • 152. Maximum Product Subarray 解答如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int SizeofNums = nums.size();
        
        if(SizeofNums == 1) {
            return nums[0];
        }
        // The largest/least product of subarray ending with the i-th element
        int maxProducts[SizeofNums];
        int minProducts[SizeofNums];
        maxProducts[0] = minProducts[0] = nums[0];
        for(int i=1; i<SizeofNums; i++) {
            // positive with positive, negative with negative, ignore previous zero
            maxProducts[i] = max( max(maxProducts[i-1]*nums[i], minProducts[i-1]*nums[i]), nums[i]);
            // positive with negative, negative with positive, ignore previous zero
            minProducts[i] = min( min(maxProducts[i-1]*nums[i], minProducts[i-1]*nums[i]), nums[i]);
        }
        
        // getting the largest product for the whole array
        int largestProduct = maxProducts[0];
        for(int i=1; i<SizeofNums; i++) {
            if(maxProducts[i] > largestProduct) {
                largestProduct = maxProducts[i];
            }
        }
        
        return largestProduct;
    }
};
  • 与上一题类似，添加额外变量，也能实现节省内存，记录子段最大乘积对应子段（$nums[startIdx, endIdx]$）的起始和终止位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int SizeofNums = nums.size();
        
        if(SizeofNums == 1) {
            return nums[0];
        }
        // The largest/least product of subarray ending with the i-th element
        int largestProduct = nums[0];
        int leastProduct = nums[0];
        // The largest product for the whole array
        int maxProduct = largestProduct;
        // subarray[startIdx, endIdx] with largest product for the whole array
        int startIdx = 0, endIdx = 0;
        // start index for largestProduct/leastProduct
        int startIdx_pos = startIdx, startIdx_neg = startIdx;
        
        for(int i=1; i<SizeofNums; i++) {
            int largestProduct_pre = largestProduct;
            int leastProduct_pre = leastProduct;
            
            // positive with positive, negative with negative, ignore previous zero
            largestProduct = max( max(largestProduct_pre*nums[i], leastProduct_pre*nums[i]), nums[i]);
            if((largestProduct_pre != nums[i]) && (largestProduct == nums[i])) {
                startIdx_pos = i;
            }
            
            // positive with negative, negative with positive, ignore previous zero
            leastProduct = min( min(largestProduct_pre*nums[i], leastProduct_pre*nums[i]), nums[i]);
            if((leastProduct_pre != nums[i]) && (leastProduct == nums[i])) {
                startIdx_neg = i;
            }
            
            if(largestProduct > maxProduct) {
                maxProduct = largestProduct;
                if(largestProduct_pre*nums[i] > leastProduct_pre*nums[i]) {
                    startIdx = startIdx_pos;
                }
                else {
                    startIdx = startIdx_neg;
                }
                endIdx = i;
            }
        }
        
        return maxProduct;
    }
};

本文标题:算法设计与分析[0009] Dynamic Programming(II)（Maximum Sum/Product Subarray）

文章作者:Gary

发布时间:2017-04-23, 14:00:22

最后更新:2020-03-28, 12:37:22

原始链接:http://durant35.github.io/2017/04/23/Algorithms_Dynamic Programming(II)/

文章目录
  1. 1. Problem Description
  2. 2. 53. Maximum Subarray 解题思路
  3. 3. 152. Maximum Product Subarray 解题思路