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

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

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

1.简述:

描述

假设你有一个数组prices,长度为n,其中prices[i]是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益

1. 你可以多次买卖该只股票,但是再次购买前必须卖出之前的股票

2. 如果不能获取收益,请返回0

3. 假设买入卖出均无手续费

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

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

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

示例1

输入:

[8,9,2,5,4,7,1]

返回值:

7

说明:

在第1天(股票价格=8)买入,第2天(股票价格=9)卖出,获利9-8=1
在第3天(股票价格=2)买入,第4天(股票价格=5)卖出,获利5-2=3
在第5天(股票价格=4)买入,第6天(股票价格=7)卖出,获利7-4=3
总获利1+3+3=7,返回7示例2

输入:

[5,4,3,2,1]

返回值:

0

说明:

由于每天股票都在跌,因此不进行任何交易最优。最大收益为0。示例3

输入:

[1,2,3,4,5]

返回值:

4

说明:

第一天买进,最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

2.代码实现:

import java.util.*;
public class Solution {
public int maxProfit (int[] prices) {
int n = prices.length;
//dp[i][0]表示某一天不持股到该天为止的最大收益,dp[i][1]表示某天持股,到该天为止的最大收益
int[][] dp = new int[n][2];
//第一天不持股,总收益为0
dp[0][0] = 0;
//第一天持股,总收益为减去该天的股价
dp[0][1] = -prices[0];
//遍历后续每天,状态转移
for(int i = 1; i < n; i++){
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
//最后一天不持股,到该天为止的最大收益
return dp[n - 1][0];
}
}

【本文来源:韩国服务器 http://www.yidunidc.com欢迎留下您的宝贵建议】
上一篇:Java中枚举类(enum)的简单使用
下一篇:没有了
网友评论