划分类DP，股票问题

2016-12-2 Bobst 2016-12-10 Bobst

划分类DP是给定原数组之后，将其划分成k个子数组，找出一个subarray，使其sum或者product最大/最小的问题。

而这类问题的 optimal substructure 是，对于给定区间的 globalMax，其最优解一定由所属区间内的 localMax 区间组成，可能不连续。 以“必须以当前结尾” 来 保证 local 子问题之间的连续性；用 global 来记录最优解之间可能的不连续性。

Kadane's Algorithm

有dp的思想在里面

def max_subarray(A):
    # in the case that the entire array consists of negative numbers
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

划分类DP 与 区间类DP 主要区别在于

我们只取其中 k 段，而中间部分可以留空； 而区间类 DP 子问题之间是连贯而不留空的。

区间类 DP 是记忆化的 divide & conquer, 划分类 DP 则是不连续 subarray 的组合。 不同于区间类 DP 每一个区间都要考虑与计算，划分类DP 很多元素和子区间是可以忽略的，有贪心法的思想在里面，因此也依赖于正确的 local / global 结构来保证算法的正确性。

Kadane's Algorithm 相比 prefix sum 的特点是，必须要以 nums[0] 做初始化，从 index = 1 开始搜，优点是在处理 prefix product 的时候更容易处理好负数的问题：“-5” 和 “0” 的情况。

这类靠 prefix sum/product 的 subarray 问题，要注意好对于每一个子问题的 local / global 最优解结构，其中 local 解都是“以当前结尾 && 连续”，而 global 未必。

Prefix sum 数组的 local / global 通用模板

求 min / max 皆可，使用时需要注意初始条件以及顺序；

    int[] leftMax = new int[n];
    int prefixSum = 0;
    int localMin = 0;
    int globalMax = Integer.MIN_VALUE;

    int index = 0;
    for(int num : nums) {
        prefixSum += num;
        // globalMax在前保证起点不会遗漏
        globalMax = Math.max(globalMax, prefixSum - localMin);
        localMin = Math.min(localMin, prefixSum);

        leftMax[index++] = globalMax;
    }

Minimum Subarray

Given an array of integers, find the subarray with smallest sum.

prefix sum 做法

维护两个变量， max 表示之前的最大的prefixSum, min 表示当前的最小的prefix subarray

public int miniSubArray(int[] nums) {
    int prefixSum = 0;
    int max = 0;
    int min = Integer.MAX_VALUE;

    for(int num : nums) {
        prefixSum += num;
        min = Math.min(min, prefixSum - max);
        max = Math.max(max, prefixSum);
    }

    return min;
}

kadane 做法

当前值要不要作为一个新起点，维护一个window，每次迭代的时候，考虑是否以当前位置为新的起点。

prevMin 始终是连续的

public int miniSubArray(int[] nums) {
    int cur = nums[0];
    int min = nums[0];

    for(int i = 0; i < nums.length; i++) {
        cur = Math.min(nums[i], cur + nums[i]);
        min = Math.min(min, cur);
    }

    return min;
}

Maximum subarray

Kadane's Algorithm

至少有一个元素

localMax 和 globalMax的关系是： 在扫描这个数组的中间，可能碰到一个很大的负数让subarray无法连续下去，必须中断，那么我们必须记录一下之前的最大值。

public int maxSubarray(int[] nums) {
    int cur = nums[0];
    int max = nums[0];

    for(int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], nums[i] + cur);
        max = Math.max(max, cur);
    }

    return max;
}

var maxSubArray = function(nums) {
    var prefix = 0;
    var max = -Infinity;
    // min是0，当没有负数的时候，一直累加就可以了
    var min = 0;

    for(var i = 0; i < nums.length; i++) {
        prefix += nums[i];
        max = Math.max(max, prefix - min);
        min = Math.min(min, prefix);
    }

    return max;
};

Maximum Product Subarray

主要有几个情况要处理：

负号： 遇到负号的时候，原本的min/max 会反转。 0：0会直接切断prefix product。开始一个新的起点。

public int maxSubarrayProduct(int[] nums) {
    int max = nums[0], min = nums[0];
    int globalMax = nums[0];

    for(int i = 1; i < nums.length; i++) {
        if(nums[i] > 0) {
            // 和当前的数来比较
            max = Math.max(nums[i], max * nums[i]);
            min = Math.min(nums[i], min * nums[i]);
        } else {
            int prevMax = max;
            max = Math.max(nums[i], min * nums[i]);
            min = Math.min(nums[i], prevMax * nums[i]);
        }

        globalMax = Math.max(globalMax, max);
    }

    return globalMax;
}

Maximum Subarray II

Given an array of integers, find two non-overlapping subarrays which have the largest sum.

枚举分割线。

这次光用 local 变量更新然后返回 global 最优还不够，我们需要保存对于每一个子问题的 global 最优（可能并不以当前位置结尾），用于后面的左右两边全局查询。

left[i] 代表从最左边到 i 位置所能取得的最大 subarray sum 是global的;

right[i] 代表从最右边到 i 位置所能取得的最大 subarray sum 是global的;

public int maxSubArrayIII(int[] nums) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];

    int prefixSum = 0;
    int prevMin = 0;
    int max = Integer.MIN_VALUE;

    for(int i = 0; i < n; i++) {
        prefixSum += nums[i];
        max = Math.max(max, prefixSum - prevMin);
        left[i] = max;
        prevMin = Math.min(prevMin, prefixSum);
    }

    prefixSum = 0;
    prevMin = 0;
    max = Integer.MIN_VALUE;

    for(int i = n - 1; i >= 0; i--) {
        prefixSum += nums[i];
        max = Math.max(max, prefixSum - prevMin);
        right[i] = max;
        prevMin = Math.min(prevMin, prefixSum);
    }

    int result = Integer.MIN_VALUE;

    for(int i = 0; i < n - 1; i++) {
        result = Math.max(result, left[i] + right[i + 1]);
    }
    return result;
}

如果用Kadane's Algo 来做

public int maxSubArrayIII(int[] nums) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];

    int localMax = nums[0];
    int globalMax = nums[0];

    left[0] = nums[0];

    for(int i = 1; i < n; i++) {
        localMax = Math.max(nums[i], localMax + nums[i]);
        globalMax = Math.max(globalMax, localMax);

        left[i] = globalMax;
    }

    localMax = nums[n - 1];
    globalMax = nums[n - 1];

    right[n - 1] = nums[n - 1;]

    for(int i = n - 2; i >= 0; i--) {
        localMax = Math.max(nums[i], localMax + nums[i]);
        globalMax = Math.max(globalMax, localMax);

        right[i] = globalMax;
    }

    int result = Integer.MIN_VALUE;

    // 枚举分割线
    for(int i = 0; i < n - 1; i++) {
        result = Math.max(result, left[i] + right[i + 1]);
    }
    return result;

}

Maximum Subarray III

find k subarrays which has largest sum

对于任意指定j，确保即使当前位置为负，作为以当前位置结尾的 localMax 依然选中此元素。因此先做一个 localMax[j - 1][j] = Integer.MIN_VALUE;

当 i = j ，即元素数 = 切分数时，即使当前元素为负，我们的 globalMax 也别无选择，必须以 localMax[i][j] 为准，采用当前元素。

local[i][k]的状态函数： max(global[i-1][k-1], local[i-1][k]) + nums[i-1]

有两种情况，第一种是第i个元素自己组成一个子数组，则要在前i－1个元素中找k－1个子数组，第二种情况是 第i个元素属于前一个元素的子数组，因此要在i－1个元素中找k个子数组（并且必须包含第i－1个元素，这样第i个元素才能合并到最后一个子数组中），取两种情况里面大的那个。

global[i][k]的状态函数： max(global[i-1][k]，local[i][k])

有两种情况，第一种是不包含第i个元素，所以要在前i－1个元素中找k个子数组，第二种情况为包含第i个元素，在i个元素中找k个子数组且必须包含第i个元素，取两种情况里面大的那个。

public int maxSubarray(int[] nums, int k) {
    int n = nums.length;

    int[] globalMax = new int[n + 1];
    int[] localMax = new int[n + 1];

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k && j <= i; j++) {
            localMax[j - 1][j] = Integer.MIN_VALUE;

            localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1]) + nums[i - 1];

            if(i == j) globalMax[i][j] = localMax[i][j];
            else globalMax[i][j] = Math.max(global[i - 1][j], local[i][j]);

        }
    }

    return globalMax[n][k];

}

Best Time to Buy and Sell Stock

only permitted to complete at most one transaction

In essence, it's find two integer which has maximum difference.

如果有两个变化的变量，我们主要是解决如何固定一个变量，让它极大或者极小。

可以用一个min变量去track一个最小值，然后go over the array, 每个数和它前面的最小值计算差值，如果能找到更小的值更新。

public int maxProfit(int[] prices) {
    if(prices == null || prices.length < 2) {
        return 0;
    }

    int n = prices.length;
    int min = prices[0];
    int max = 0;

    for(int i = 1; i < n; i++) {
        max = Math.max(prices[i] - min, max);
        min = Math.min(prices[i],min);
    }
    return max;
}

Best Time to Buy and Sell Stock II

You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times).

Code

// 因为不限制交易的次数，所以只要股票的价格提高了，我们就卖出。
public int maxProfit(int[] prices) {
    if(prices == null || prices.length < 2) {
        return 0;
    }

    int profit = 0;

    for(int i = 1; i < prices.length; i++) {
        if(prices[i] - prices[i - 1] > 0) {
            profit += prices[i] - prices[i - 1];
        }
    }

    return profit;
}

Best Time to Buy and Sell Stock III

You may complete at most two transactions.

Analyze

最多交易两次，意味着我们可以把array分成两部分，一边代表一次交易，所以我们需要枚举这个分割线的位置。

Code

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) {
            return 0;
        }

        int n = prices.length;

        int[] left = new int[n]; // 到当前为止，最大的利润
        int[] right = new int[n];

        // prices[1,2,3,4,5]
        // 当i = 2相当从2这里把数组分成两半
        // left[2] 等效数组 prices[1,2]
        // right[2] 等效数组 prices[2,3,4,5] 

        int min = prices[0];
        left[0] = 0; // 第一天不能交易
        for(int i = 1; i < n; i++) {
            min = Math.min(prices[i], min);
            left[i] = Math.max(prices[i] - min, left[i - 1]);
        }

        int max = prices[n - 1];
        right[n - 1] = 0; // 等效数组只有一个元素，所以没有利润
        for(int i = n - 2; i >= 0; i--) {
            max = Math.max(max, prices[i]);
            right[i] = Math.max(max - prices[i], right[i + 1]);
        }

        int result = 0;
        // iterate the partition line
        for(int i = 0; i < n; i++) {
            result = Math.max(result, left[i] + right[i]);
        }

        return result;
    }
}