dp算法 力扣123 买卖股票的最佳时机 III

简介: dp算法 力扣123 买卖股票的最佳时机 III

本文是Java代码编写

123. 买卖股票的最佳时机 III - 力扣(LeetCode)

一、题目详情

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:


输入:prices = [3,3,5,0,0,3,1,4]

输出:6

解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。

    随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。



示例 2:


输入:prices = [1,2,3,4,5]

输出:4

解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  

    注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。  

    因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。


示例 3:


输入:prices = [7,6,4,3,1]

输出:0

解释:在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4:


输入:prices = [1]

输出:0


提示:


1 <= prices.length <= 105

0 <= prices[i] <= 105

二、算法讲解

根据题目可知,购买股票最多两笔交易(即买入和卖出分别最多两次),故我们可以将dp表以买入和卖出两种状态区分开来,即设两个不同的表表示不同的状态,同时不同的交易的次数代表不同的一维下标:
f[i][j]表示:第i天第j次交易的买入状态;

g[i][j]表示:第i天第j次交易的卖出状态;

根据买入和卖出状态,可推导状态转移方程

 f[i][j] = Math.max(f[i-1][j],g[i-1][j]-prices[i]);

g[i][j] = Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
对于边界值(i-1,j-1),对于i-1我们使用增加虚拟节点的方式,其交易情况由自己导入,j-1使用判断避免其越界。

返回值是g[i][j]数组中位于最后一行中最大的那一个数。

三、代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        int max = Integer.MIN_VALUE;
        for(int i=0;i<3;i++){
            g[0][i] = -0x3f3f3f3f;
            f[0][i] = -0x3f3f3f3f;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for(int i=1;i<n;i++){
            for(int j=0;j<3;j++){
                if(j-1>=0){
                    g[i][j] = Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
                }else{
                     g[i][j] = g[i-1][j];
                }
                f[i][j] = Math.max(f[i-1][j],g[i-1][j]-prices[i]);               
            }
        }
        for(int i=0;i<3;i++){
            max = Math.max(max,g[n-1][i]);
        }
        return max;
    }
}

运行截图:



结语

这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!

相关文章
|
6月前
|
算法 Python
【Leetcode刷题Python】309. 最佳买卖股票时机含冷冻期
解决LeetCode上309题“最佳买卖股票时机含冷冻期”的Python代码示例,利用动态规划方法计算在含有冷冻期约束下的最大利润。
53 1
|
6月前
|
算法 Python
【Leetcode刷题Python】121. 买卖股票的最佳时机
解决LeetCode上121题“买卖股票的最佳时机”的Python代码示例,采用一次遍历的方式寻找最佳买卖时机以获得最大利润。
77 1
|
6月前
|
算法
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
80 0
|
6月前
|
算法 Python
【Leetcode刷题Python】714. 买卖股票的最佳时机含手续费
提供了两种解决买卖股票最佳时机含手续费问题的Python实现方法:贪心算法和动态规划算法。
63 0
|
6月前
|
算法 Python
【Leetcode刷题Python】122.买卖股票的最佳时机 II
LeetCode "买卖股票的最佳时机 II" 问题的Python代码实现,采用贪心算法在股票价格上升的每一天买入并卖出,以获得最大利润。
40 0
|
8月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
8月前
|
算法
leetcode题解:121.买卖股票的最佳时机
leetcode题解:121.买卖股票的最佳时机
54 0
|
30天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
30天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
144 68
|
1月前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。