当前位置 : 主页 > 编程语言 > java >

#yyds干货盘点# 面试必刷TOP101:买卖股票的最好时机(三)

来源:互联网 收集:自由互联 发布时间:2022-10-14
1.简述: 描述 假设你有一个数组prices,长度为n,其中prices[i]是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益1. 你最多可以对该股票有两笔交易操作,

1.简述:

描述

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

数据范围:#yyds干货盘点# 面试必刷TOP101:买卖股票的最好时机(三)_时间复杂度,股票的价格满足 #yyds干货盘点# 面试必刷TOP101:买卖股票的最好时机(三)_时间复杂度_02

要求: 空间复杂度 #yyds干货盘点# 面试必刷TOP101:买卖股票的最好时机(三)_数组_03,时间复杂度 #yyds干货盘点# 面试必刷TOP101:买卖股票的最好时机(三)_数组_03

进阶:空间复杂度 #yyds干货盘点# 面试必刷TOP101:买卖股票的最好时机(三)_空间复杂度_05,时间复杂度 #yyds干货盘点# 面试必刷TOP101:买卖股票的最好时机(三)_数组_03

示例1

输入:

[8,9,3,5,1,3]

返回值:

4

说明:

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

输入:

[9,8,4,1]

返回值:

0

示例3

输入:

[1,2,8,3,8]

返回值:

12

说明:

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

2.代码实现:

import java.util.*;
public class Solution {
public int maxProfit (int[] prices) {
int n = prices.length;
int[][] dp = new int[n][5];
//初始化dp为最小
Arrays.fill(dp[0], -10000);
//第0天不持有状态
dp[0][0] = 0;
//第0天持有股票
dp[0][1] = -prices[0];
//状态转移
for(int i = 1; i < n; i++){
dp[i][0] = dp[i - 1][0];
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
//选取最大值,可以只操作一次
return Math.max(dp[n - 1][2],Math.max(0, dp[n - 1][4]));
}
}
上一篇:tsconfig之jsx属性
下一篇:没有了
网友评论