题解 | JAVA DP #买卖股票的最好时机(一)# [P0]

介绍两种时间O(n), 空间O(1)的解法

第一种(更符合DP思维):

定义F[i]: 在第i天持有股票的最大浮盈

情况1: 第i-1天已经持有股票，那么第i天继续持有的浮盈就是i-1天的浮盈加上i和i-1的价差： 
  F[i-1]+(P[i]-P[i-1])
情况2: 第i-1天未持有，第i天买入，此时浮盈为0

所以F[i] = max(情况1，情况2) = max(F[i-1]+(P[i]-P[i-1]), 0)
可见计算F[i]只需要昨天的state, 所以空间可以优化到O(1)

import java.util.*;

public class Solution {
    public int maxProfit (int[] prices) {
      if (prices.length <= 1) return 0;
      
      // F(i): maximum unrealized gain when holding stock at day i.
      // F(i) = max{ F(i-1) + (p[i] - p[i-1]), 0 }
      int max = 0, f = 0;
      for (int i = 1; i < prices.length; i++) {
        f = Math.max(f + (prices[i] - prices[i-1]), 0);
        max = Math.max(max, f);
      }
      
      return max;
    }
}

第二种(更容易理解):

记录之前最低股价和最大盈利

import java.util.*;

public class Solution {
    public int maxProfit (int[] prices) {
      int min = Integer.MAX_VALUE;
      int maxProfit = 0;
      
      for (int p : prices) {
        maxProfit = Math.max(maxProfit, p - min);
        min = Math.min(p, min);
      }
      
      return maxProfit;
    }
}