写点什么

代码随想录 Day49 - 动态规划(十)

作者:jjn0703
  • 2023-08-22
    江苏
  • 本文字数:1144 字

    阅读完需:约 4 分钟

作业题

121. 买卖股票的最佳时机

链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/22 23:36 */public class LeetCode121 { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) return 0; int length = prices.length; // dp[i][0]代表第i天持有股票的最大收益 // dp[i][1]代表第i天不持有股票的最大收益 int[][] dp = new int[length][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < length; i++) { dp[i][0] = Math.max(dp[i - 1][0], -prices[i]); dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]); } return dp[length - 1][1]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] prices = new int[count]; for (int i = 0; i < count; i++) { prices[i] = scanner.nextInt(); } int maxProfit = new LeetCode121().maxProfit(prices); System.out.println(maxProfit); }}
复制代码

122. 买卖股票的最佳时机 II

链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/22 23:43 */public class LeetCode122 { public int maxProfit(int[] prices) { int n = prices.length; // 创建二维数组存储状态 int[][] dp = new int[n][2]; // 初始状态 dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; ++i) { // 第 i 天,没有股票 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 第 i 天,持有股票 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] prices = new int[count]; for (int i = 0; i < count; i++) { prices[i] = scanner.nextInt(); } int maxProfit = new LeetCode122().maxProfit(prices); System.out.println(maxProfit); }}
复制代码


发布于: 刚刚阅读数: 3
用户头像

jjn0703

关注

Java工程师/终身学习者 2018-03-26 加入

USTC硕士/健身健美爱好者/Java工程师.

评论

发布
暂无评论
代码随想录Day49 - 动态规划(十)_jjn0703_InfoQ写作社区