Leetcode-121 Best Time to Buy and Sell Stock

Description

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

动态规划

分治和动态规划：不相交的子问题、相交的子问题

从斐波那契开始

最优解 vs 最优解的值

朴素递归 —— 自顶向下

因为子问题一般是重叠的，采用自顶向下的方式计算最优解的值会重复对多个相同的子问题求解，时间复杂度和空间复杂度都会指数增长。而自底向上的求解过程是递推式的进行，会先计算最基础的子问题，然后将子问题的结果缓存（可以仅仅缓存和下一个状态相关的子问题的解），所以我们一般采用自底向上的方式求解最优解的值。

带备忘录的自顶向下

一般步骤：

1. 刻画一个最优解的结构特征。
2. 递归定义最优解的值。
3. 计算最优解的值，通常采用自底向上的方法。
4. 利用计算出的信息构造一个最有解（可选）。

程序设计

class Solution {
    public int maxProfit(int[] prices) {
        if (null == prices || prices.length == 0) {
            return 0;
        }
        
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            dp[i] = Math.max(dp[i-1], prices[i]-min);
        }
        
        return dp[prices.length - 1];
    }
}

内存优化

class Solution {
    public int maxProfit(int[] prices) {
        if (null == prices || prices.length == 0) {
            return 0;
        }
        
        int profit = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            profit = Math.max(profit, prices[i]-min);
        }
        
        return profit;
    }
}

LIS 数量

1. 定义问题

   给定一个序列 $ X = <x_1, x_2, …, x_n> $，如果 $ Z = <z_1, z_2, … z_i> $ 是 X 的子序列，且满足：

   $ z_i > z_(i-1) $，则 Z 是 X 的递增子序列 ，其中元素最多的递增子序列叫做 X 的最长递增子序列 (LIS)

2. 刻画 LIS 的特征

   假设 $ Z = <z_1, z_2, … z_i> $ 是 X 的一个 LIS，

   • 那么 $Z_i > Z_(i-1)$

3. 求 LIS 的长度

TODO LIST

1. https://leetcode.com/problems/number-of-longest-increasing-subsequence/

2. https://leetcode.com/problems/longest-arithmetic-sequence/

3. https://leetcode.com/problems/predict-the-winner/
4. https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
5. https://leetcode.com/problems/filling-bookcase-shelves/

DP AC

• https://leetcode.com/problems/longest-continuous-increasing-subsequence/submissions/

• https://leetcode.com/problems/delete-operation-for-two-strings/

• https://leetcode.com/problems/number-of-longest-increasing-subsequence/