【Java】 剑指offer(63) 股票的最大利润

时间:2021-07-21 14:58:40

 

本文参考自《剑指offer》一书,代码采用Java语言。

更多:《剑指Offer》Java实现合集  

题目

  假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖交易该股票可能获得的利润是多少?例如一只股票在某些时间节点的价格为{9, 11, 8, 5,7, 12, 16, 14}。如果我们能在价格为5的时候买入并在价格为16时卖出,则能收获最大的利润11。

思路

  遍历每一个数字,并保存之前最小的数字,两者差最大即为最大利润。

  值得注意的是,我自己一开始写的代码是默认不能亏本(即可以不买入卖出,利润不能为负数),所以比较简单;但如果可以亏本,最大利润指的是最小的亏损,那么要注意最小数字不能是最后一个。在下面的代码中可以注意比较两种情况的差别。可以考虑的例子如 { 16, 11, 7, 4, 2, 1 }

测试算例 

  1.功能测试(数组递增/递减/无序)

  2.特殊测试(null,空数组)

  3.边界值测试(数组仅两个数字)

Java代码

//题目:假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖交易该股
//票可能获得的利润是多少?例如一只股票在某些时间节点的价格为{9, 11, 8, 5,
//7, 12, 16, 14}。如果我们能在价格为5的时候买入并在价格为16时卖出,则能
//收获最大的利润11。 public class MaximalProfit {
public static int MaxDiff(int[] arr) {
if(arr==null || arr.length<2)
return -1; //error
int min=arr[0]; //最大利润可以是负数,只要亏损最小就行
int maxDiff=arr[1]-min;
for(int i=1;i<arr.length;i++) {
if(arr[i-1]<min) //保存“之前”最小数字
min=arr[i-1];
if(arr[i]-min>maxDiff)
maxDiff=arr[i]-min;
} //默认不能亏本,代码简单,上面复杂的代码注意细节
// int maxDiff=0;
// for(int i=1;i<arr.length;i++) {
// if(arr[i]<min)
// min=arr[i];
// else if(arr[i]-min>maxDiff)
// maxDiff=arr[i]-min;
// }
return maxDiff;
} //简单快速测试下
public static void main(String[] args) {
int[] arr1=null;
System.out.println(MaxDiff(arr1)==-1); int[] arr2={ };
System.out.println(MaxDiff(arr2)==-1); int[] arr3={ 16, 16, 16, 16, 16 };
System.out.println(MaxDiff(arr3)==0); int[] arr4={ 1, 2, 4, 7, 11, 16 };
System.out.println(MaxDiff(arr4)==15); int[] arr5={ 16, 11, 7, 4, 2, 1 };
System.out.println(MaxDiff(arr5)==-1); int[] arr6={ 9, 11, 5, 7, 16, 1, 4, 2 };
System.out.println(MaxDiff(arr6)==11); int[] arr7={ 2,4};
System.out.println(MaxDiff(arr7)==2); int[] arr8={ 4,2};
System.out.println(MaxDiff(arr8)==-2);
}
}

  

true
true
true
true
true
true
true
true

MaximalProfit

收获

  1.蛮力法时间复杂度为O(n^2),肯定不对。我们从头到尾遍历,确定规律。可以发现找出之前的最小值即可。

 

更多:《剑指Offer》Java实现合集  

【Java】 剑指offer(63) 股票的最大利润的更多相关文章

  1. 剑指 Offer 63&period; 股票的最大利润 &plus; 动态规划

    剑指 Offer 63. 股票的最大利润 Offer_63 题目描述 方法一:暴力法 package com.walegarrett.offer; /** * @Author WaleGarrett ...

  2. 剑指offer——73股票的最大利润

    题目: 假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?例如,一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}.如果我们能在价格为5 ...

  3. 剑指Offer 63&period; 数据流中的中位数(其他)

    题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值.如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值.我们 ...

  4. &lbrack;剑指Offer&rsqb; 63&period;数据流中的中位数

    题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值.如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值. c ...

  5. LeetCode:&OpenCurlyDoubleQuote;剑指 Offer”

    LeetCode:"剑指 Offer" 刷题小菜鸡,花了几天时间做了一遍 LeetCode 上给出的 "剑指 Offer" 在此做一下记录 LeetCode主页 ...

  6. 剑指offer二刷(精刷)

    剑指 Offer 03. 数组中重复的数字 题目描述 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内.数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次. ...

  7. LeetCode—剑指 Offer学习计划

    第 1 天 栈与队列(简单) 剑指 Offer 09. 用两个栈实现队列 class CQueue { public: CQueue() { } stack<int>s1,s2; void ...

  8. 剑指Offer (汇总)

    刷完剑指Offer很久了,前几天想起来去年开通的博客园,正好把刷题笔记整理一下 刷题平台:牛客网 刷题语言:Python **链表(8道)** [剑指Offer 3. 从尾到头打印链表 (链表)](h ...

  9. 【剑指offer】(第 2 版)Java 题解

    [剑指offer](第 2 版)Java 题解 第一章 面试的流程 略... 第二章 面试需要的基础知识 面试题 1. 赋值运算符函数 面试题 2. 实现 Singleton 模式 Solution ...

随机推荐

  1. vb中&amp&semi;和&plus;的区别

    在字符串连接时+号只能是两个字符串线连接&号可以是字符串与另一种类型的数据相连接.例如"a"+"b"是合法的,而 "a"+2是错误的 ...

  2. 【转】XML之命名空间的作用&lpar;xmlns&rpar;

    原文链接:http://blog.csdn.net/zhch152/article/details/8191377 命名空间的作用,下面的内容是转载的,大家可以看看:   问题的出现:XML的元素名字 ...

  3. js----方法是否加括号的问题

    在我们js编写程序的时候,我们会写很多函数然后调用它们,那么这些函数调用的时候什么时候加()什么时候不加()?记住以下几个要点. (1)函数做参数时都不要括号. function fun(e) { a ...

  4. hdu 4501 小明系列故事——买年货&lowbar;二维背包

    题目:你可以有v1元,v2代金券,v3个物品免单,现在有n个商品,商品能用纸币或者代金券购买,当然你可以买v3个商品免费.问怎么最大能买多少价值 题意: 思路二维背包,dp[v1][v2][v3]=M ...

  5. 打包程序时的证书问题&lpar;上传APP就出现Missing iOS Distribution signing indetity for&rpar;

    现象: 解决办法: 1.删除本地钥匙串中的这个文件,注意“系统”中的同名文件也必须删除 2.进入http://www.apple.com/certificateauthority/ 下载新的(WWDR ...

  6. Django的form表单之文件上传

    在生成input标签的时候可以指定input标签的类型为file类型 <!DOCTYPE html> <html lang="en"> <head&g ...

  7. Tomcat中虚拟路径

    默认情况下,Tomcat访问静态资源配置是这样的 <Context path="/project_name" docBase="d:\tomcat_statics& ...

  8. 自制 Python小工具 将markdown文件转换成Html文件

    今天看到了一个Python库,名为markdown.瞬间就给了我一个灵感,那就是制作一个将markdown文件转换成html文件的小工具. 我的实验环境 操作系统: Windows 7 64位 旗舰版 ...

  9. LeetCode之&OpenCurlyDoubleQuote;数学”:Plus One

    题目链接 题目要求: Given a non-negative number represented as an array of digits, plus one to the number. Th ...

  10. etcd 启动错误

    Apr 26 16:17:25 ceph-0 etcd: f281dc69fb4dd3d8 became candidate at term 3574Apr 26 16:17:25 ceph-0 et ...