2025年- H75-Lc183--121.买卖股票的最佳时机1(贪心or动态规划）--Java版

1.题目描述

2.思路

（1）贪心
局部最优的思想，每次收获每天的正利润。
全局最优：由局部最优得到。
索引要从1开始（因为第0天是买，第1天是卖）
result=max（price[i]-price[i-1],0)

前两天利润是负数，所以直接取0

（2）动态规划
1）dp[i][0]:持有股票的最大现金（可能在i的前几天买了这个股票，第i天只是拥有持有股票的状态）
dp[i][1]:不持有股票的最大现金的状态（可能是在第i天卖出，也可能是前几天卖出，只是维持这个不持有股票的状态）
最终结果在这两个数组中取一个最大值：dp[n-1][0],dp[n-1][1]取一个最大值。
2）dp[i-1][0]:在第i-1天还是持有股票的状态。-price[i]:或者再第i天才买入股票。求二者之间的最大值dp[i][0]=max(dp[i-1][0],-price[i])
如果再第i天就把股票卖了，所以再i-1天股票是保存有的状态，dp[i][1]=dp[i-1][0]+prices[i]. 所以可以得到递推公式dp[i][1]=max（dp[i-1][1],dp[i-1][0]+price[i])
3)dp数组初始化。
dp[0][0]=0-price[0]
dp[0][1]=0;
4）遍历顺序：从前往后的顺序（后面的状态依赖于前面的状态）
for（i=1；i<len；i++) 因为i=0已经在第三步初始化了。
5）输出max（dp[n-1][0],dp[n-1][1])
不持有股票的手上现金会多
最后打印一下dp数组

3.代码实现

public class H121 {public int maxProfit(int[] prices) {int  result=0;int minPrice = Integer.MAX_VALUE;for(int i=0;i<prices.length;i++){if(prices[i]<minPrice){minPrice=prices[i];}else {result =  Math.max(prices[i] - minPrice, result);}}return result;}public static void main(String[] args){H121 test=new H121();int[] price={7,1,5,3,6,4};int res=test.maxProfit(price);System.out.print(res);}}