#yyds干货盘点# 动态规划专题：买卖股票的最好时机(三)

sunshine lv.1

发布时间：2022-11-14 17:03:33 299

相关标签：

1.简述：

描述

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票2. 如果不能获取收益，请返回03. 假设买入卖出均无手续费

数据范围：股票的价格满足

要求: 空间复杂度，时间复杂度

进阶：空间复杂度，时间复杂度

输入描述：

第一行输入一个正整数 n ，表示数组 prices 的长度

第一行输入 n 个正整数，表示数组 prices 的所有元素的值

输出描述：

输出最大收益

示例1

输入：

6
8 9 3 5 1 3

输出：

说明：

第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2
总收益为4。

示例2

输入：

4
9 8 4 1

输出：

示例3

输入：

5
1 2 8 3 8

输出：

说明：

第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。
因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。

2.代码实现：

import java.util.*;

public class Main {
    public static void main (String[] args) {
        // 1. 状态
        // 买入状态,卖出状态

        // 2. 选择
        // 买入,卖出,不动
        // 只能操作两笔
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int price = sc.nextInt();
      
        // 3. dp定义
        // buy1 代表第1次买入的股票收益
        // sell1代表第1次卖出的股票收益
        // buy2 代表第2次买入的股票收益
        // sell2代表第2次卖出的股票收益
      
        // 4. 基本状态
        // buy1=-price, sell1=0
        // buy2=-price, sell2=0
        int buy1 = -price, sell1 = 0;
        int buy2 = -price, sell2 = 0;
        
        for (int i = 1; i < n; i++) {
            price = sc.nextInt();
            // 5. 转移方程
            buy1  = Math.max(buy1, - price);
            sell1 = Math.max(sell1, buy1 + price);
            buy2  = Math.max(buy2, sell1 - price);
            sell2 = Math.max(sell2, buy2 + price);
        }
        System.out.println(sell2);
    }
}

文章来源： https://blog.51cto.com/u_15488507/5841938

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。