Template: maximum for example

• globalMax, localMin, prefixSum

int[] leftMax = new int[n];

int globalMax = Integer.MIN_VALUE;
int prefixSum = 0;
int localMin = 0;

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

    leftMax[i] = globalMax;
}

Maximum Subarray:

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxSum = Integer.MIN_VALUE;
        int sum = 0;
        int minPrefixSum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            maxSum = Math.max(maxSum, sum - minPrefixSum);
            minPrefixSum = Math.min(minPrefixSum, sum);
        }

        return maxSum;
    }

• segment tree

Maximum Subarray ii - left and right

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

    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        // write your code
        if (nums == null || nums.size() == 0) return 0;

        int n = nums.size();
        int[] left = new int[n];
        int[] right = new int[n];

        int sum = 0;
        int max = Integer.MIN_VALUE;
        int minPrefixSum = 0;

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

        sum = 0;
        max = Integer.MIN_VALUE;
        minPrefixSum = 0;

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

        max = Integer.MIN_VALUE;

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

        return max;
    }

Maximum Subarray iii - k non-overlapping subarrays

• DP

Minimum Subarray

Best Time to Buy and Sell Stock - only one transaction

• here price is the sum, minPrefixSum is the minPrice
• same as maximum subarray
• max = 0, not integer.min
• i can start from 1

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

        int max = 0;
        int minPrice = prices[0];   // min prefix sum

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

Best Time to Buy and Sell Stock ii - multiple transactions, k non-overlapping

• only buy stock when profitable
• cf maximum subarray iii, k is given as input, but here k can be any.

public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            int diff = prices[i+1] - prices[i];
            if (diff > 0) {
                profit += diff;
            }
        }
        return profit;
    }
}

Best Time to Buy and Sell Stock iii - one or two transactions

• maximum subarray ii
• max is 0 not integer.min
• left[i] : 从最左面到 i 所能获得的最大利益（单次交易）
• 每个位置并不是非交易不可，需要用 0 来代表不做交易的情况；
• 不是非要做 “两次交易” 不可，因此 left[end] 作为一次交易的代表，也要考虑在内。(or right[start])

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

        int n = prices.length;
        int[] left = new int[n];
        int[] right = new int[n];

        int max = 0;
        int minPrice = prices[0]; // min prefix sum

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

        // 相当于沽空 所以求min
        int min = 0;
        int maxPrice = prices[prices.length - 1]; // max prefix sum
        right[prices.length - 1] = 0;

        for (int i = n - 1; i >= 0; i--) {
            min = Math.min(min, prices[i] - maxPrice);
            maxPrice = Math.max(maxPrice, prices[i]);
            right[i] = min;
        }

        int profit = 0;
        for (int i = 0; i < n - 1; i++) {
            // 注意是 - 
            profit = Math.max(profit, left[i] - right[i + 1]);
        }

        // might be completely on one side;
        profit = Math.max(profit, left[n-1]);
        //profit = Math.max(profit, -right[0]);
        return profit;
    }

Maximum subarray difference

• leftMax[], leftMin[], rightMax[], rightMin[]
• max(abs(leftMax[i] - rightMin[i+1]), abs(leftMin[i] - rightMax[i+1]))

Subarray Sum

• hashmap
• 2 for loop o(n^2)

Subarray sum closest

• store all prefix sum, then sort
• the closest sum should be a number that is between 2 adjacent element.