股票的最大利润(剑指offer 63)Java动态规划

简介: 假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

一、题目描述



假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?


示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。

   

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。


示例 2:

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

输出: 0

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

 

限制:

0 <= 数组长度 <= 10^5


二、思路讲解


       

比较典型的动态规划问题,按照天数增长,计算出第一天到当天的最大利润。

     

第一天到当天的最大利润 = max{前一天的最大利润, 今天的价格-历史最低价} 。

       

考虑极端情况,如果传入的数组为空,直接返回0。


三、Java代码实现



class Solution {
    public int maxProfit(int[] prices) {
        //考虑数组为空的情况
        if(prices.length == 0){
            return 0;
        }
        int len = prices.length;    //天数
        int dp = 0;                 //记录当前最大利润
        int min = prices[0];        //记录当前最小价格
        //计算出第一天到第i天的最大利润
        for(int i=1; i<len; i++){
            min = Math.min(prices[i], min);
            dp = Math.max((prices[i]-min), dp);
        }
        //返回
        return dp;
    }
}


四、时空复杂度分析



时间复杂度:        O(N)         需要遍历一遍prices数组

空间复杂度:        O(1)


相关文章
|
9月前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
226 5
剑指offer_3_前n个数字二进制形式中1的个数(java)
剑指offer_3_前n个数字二进制形式中1的个数(java)
剑指offer_2_二进制加法(java)
剑指offer_2_二进制加法(java)
剑指offer_1_整数除法(java)
剑指offer_1_整数除法(java)
124 0
|
算法 Java 决策智能
Java数据结构与算法:动态规划之背包问题
Java数据结构与算法:动态规划之背包问题
|
存储 安全 Java
剑指offer全集系列Java版本(2)
剑指offer全集系列Java版本(2)
98 0
|
存储 Java
剑指offer全集系列Java版本(1)
剑指offer全集系列Java版本(1)
98 0
|
算法 Java C++
刷题两个月,从入门到字节跳动offer丨GitHub标星16k+,美团Java面试题
刷题两个月,从入门到字节跳动offer丨GitHub标星16k+,美团Java面试题
|
Java
0-1背包问题(Java详解)(动态规划)至少与恰好
0-1背包问题(Java详解)(动态规划)至少与恰好
164 1
|
算法 Java 索引
[Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读
[Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读
92 0

热门文章

最新文章