【数组】买卖股票的最佳时机

做题思路：双指针（快、慢）成功！

1. 若数组长度为1，返回0
2. 创建两个指针p1和p2，p1指向第一个元素（慢指针），p2指向第二个元素（快指针）。
3. 当price[p2]不为NULL时循环：
   1. 若p1指向元素的值大于或等于p2指向元素的值，p1和p2均后移；
   2. 否则，p2向后移，每次后移之后与前一位元素进行比较，若前一位元素值较大，则让sum+=price[p2-1]-price[p1]
   3. 让p1=p2，p2后移一位
4. 若此时p2-1≠p1，则sum+=price[p2-1]-price[p1]

int maxProfit(int* prices, int pricesSize){
    int sum = 0;
    if(pricesSize == 1)
        return sum;
    int p1 = 0;
    int p2 = 1;
    while(p2 < pricesSize) {
        if(prices[p1] >= prices[p2]) {
            p1++;
            p2++;
        } 
        else {
            p2++;
            if(p2<pricesSize && prices[p2-1] >=prices[p2]) {
                sum+=(prices[p2-1] - prices[p1]);
                p1 = p2;
                p2++;
            }
        }
    }
    if((p2-1) != p1)
        sum+=(prices[p2-1] - prices[p1]);
    return sum;
}

官方解法：动态规划

算法思想：

1. 定义一个二维数组dp[i][j]代表资金状态
   • i表示天数，j表示持股状态（j为0表示持有现金，j为1表示持有股票）
   • dp[i][j]表示到i天，持股状态为j时，我们手上的最大现金数
2. 状态从持有资金开始，到最后一天我们仍然关心持有资金
   • 每一天状态可以转换，也可以不动
3. 初始值为dp[0][0] = 0;dp[0][1] = -prices[0]
4. 终止时，输出dp[len-1][0]（最后一天卖掉股票保证受益最大化）

public class Solution {

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

        // 0：持有现金
        // 1：持有股票
        // 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0
        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            // 这两行调换顺序也是可以的
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }
}

int maxProfit(int* prices, int pricesSize){
	if(pricesSize <=1)
		return 0;
	int dp[pricesSize][2] = {0};
	dp[0][0] = 0;
	dp[0][1] = 0 - prices[0];
	for(int i =1;i < pricesSize;i++) {
		//假设在第i-1天买了股票：现有资产为dp[i-1][1]，若此时卖掉股票无法回本（dp[i-1][1]+prices[i] < dp[i-1][0]），则不买股票，赋值dp[i-1][0]。若能盈利，就应在i-1天买股票，此时收益为dp[i][1]
		dp[i][0] = getMax(dp[i-1][0], dp[i-1][1] + prices[i]);
		dp[i][1] = getMax(dp[i-1][1], dp[i-1][0]-prices[i]);
	}
	return dp[pricesSize-1][0];
}

int getMax(int a, int b) {
	if(a>b)
		return a;
	return b;
}