//状态机或者说是动态规划，看题解过程更好理解
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0 || prices == null){
return 0;
}
int n = prices.length;
int[][] dp = new int[n][2];
for(int i = 0; i < n; i++){
if(i - 1 == -1){
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[n - 1][0];
}
}
题解过程： [7,1,5,3,6,4]
dp[0][0] = 0, dp[0][1] = -7
dp[1][0] = max(0, -7 + 1) = 0, dp[1][1] = max(-7, -1) = -1;
dp[2][0] = max(0, -1 + 5) = 4, dp[2][1] = max(-1, -5) = -1;
dp[3][0] = max(4, -1 + 3) = 4, dp[3][1] = max(-1, -3) = -1;
dp[4][0] = max(4, -1 + 6) = 5, dp[4][1] = max(-1, -6) = -1;
dp[5][0] = max(5, -1 + 4) = 3, dp[5][1] = max(-1, -4) = -1;
时间复杂度：O(n)
空间复杂度：O(k)
//优化
因为发现了新状态只和相邻的一个状态有关，我就不用把每一个存储，而是用两个变量 x 和 y 存储
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0 || prices == null){
return 0;
}
int n = prices.length;
int x = 0, y = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
x = Math.max(x, y + prices[i]);
y = Math.max(y, -prices[i]);
}
return x;
}
}
时间复杂度：O(n)
空间复杂度：O(1)
