本文主要是介绍[剑指Offer]-股票的最大利润,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可获得的最大利润是多少?
例如,一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出,则能获得最大的利润为11.
解题思路
- 暴力比较:时间复杂度O(n^2)
- 最大利润无外乎就是计算后面的数字减去前面的数字得到的一个最大的差值,当我们确定卖出价后,只需要找到一个最小的买入价即可
- 最小买入价格,当前利润,最大利润。时间复杂度O(n)
算法图解
参考代码:
package offer;/*** 股票的最大利润* 例如,一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出,则能获得最大的利润为11.*/
public class Offer63 {public static void main(String[] args) {int nums[] = {9, 11, 8, 5, 7, 12, 16, 14};System.out.println(maxDiff(nums));}static int maxDiff(int nums[]) {if (nums == null) {return 0;}// 最小买入int minbugIn = nums[0];//最大利润int maxDiff = nums[1] - minbugIn;for (int i = 2; i < nums.length; i++) {if (nums[i-1] < minbugIn) {minbugIn = nums[i];}int currentDiff=nums[i]-minbugIn;if(currentDiff>maxDiff){maxDiff=currentDiff;}}return maxDiff;}}
附录
该题源码在我的 ?Github 上面!
这篇关于[剑指Offer]-股票的最大利润的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!