admin 管理员组

文章数量: 887007

动态规划：股票买卖问题（只交易一次）——07

股票买卖问题（只交易一次）

问题描述

算法思路

  • 其实这道题目思想很简单，无非就是要找到股票的最大值和最小值，并且保证最大值一定在最小值的右边

  • 动态规划思想：从最后一步来看问题

    • 设F（n）为前n天交易可获得的最大利润，price【】为输入数组

    • 当我们要求F（n）的时候，就看看和F（n-1）有没有关系，此时有两种情况

      • M1 = price【n】 - MIN { price【0 - n-1】}
      • M2 = F（n - 1）
      • M1为当天价格减去前几天的最低价可获得的最大陆润
      • M2为不算当天价格可以获得的最大利润
      • 最终F（n） = MAX {M1, M2}

  • 到这里我们就很清楚了，动态规划的三要素如下：

    • 子问题：减少天数的子问题

    • 最优子结构：前n天的最大利润

    • 状态转移方程：

      • F（n） = MAX {price【n】 - MIN { price【0 - n-1】} , F（n - 1）}

  • 但是目前我们需要知道我们的dp矩阵存储的是什么？通过分析发现，我们每次需要知道 前n天能交易的最大利润 和 前n天的最低价格 这里两个参数。但是实际上dp矩阵只能存储一种数据的参数。

  • 这里我们设计的dp【i】存储前 i 天的最低价格，而前 i 天交易的最大利润则使用变量来进行存储

实现

public static int maxstock(int[] price){int[] dp  = new int[price.length];dp[0] = price[0];int maxVaule = 0;for(int i = 1; i < price.length; i++){if(price[i] - dp[i - 1] > maxVaule) maxVaule = price[i] - dp[i - 1];if(price[i] < dp[i - 1]) {dp[i] = price[i];}else {dp[i] = dp[i - 1];}}return maxVaule;}

本文标签： 动态规划股票买卖问题（只交易一次）07

版权声明：本文标题：动态规划：股票买卖问题（只交易一次）——07 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732353239h1533694.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。