面试题——股票利益最大化

1. 题目

给出一个包含N个元素的数组,数组中的每个元素代表每一天的股票的买卖价格。现在给你个任务是在任意的时刻先买股票,之后卖出股票。要求是使得买卖股票的利益最大化,算法的时间和空间复杂度尽可能达到最优。

2. 解题思路

看到本题,绝大多数人的第一思路大概都能想到用最大值去减最小值。但是问题出来了,最小值出现的位置不一定在最大值出现的位置前面,这样就违背了先买后卖的现实规律。

对于这个问题,为了保证最小值出现在当前最高价格之前。正确的思想应该是假设任意时刻都是可以卖的时间点,在这之前的最低价买入,扫描整个数组之后,整体的最大利益就能够计算出来!

3. 代码示例

public class Demo {
    public static void main(String[] args) {

        int[] nums = {
            4, 5, 6, 9, 26, 39, 1, 
            18, 24, 21, 19, 33};

        int min = nums[0];
        int maxProfit = 0;

        for (int num : nums) {
            if (num < min) {
                min = num;
            }

            if (num - min > maxProfit) {
                maxProfit = num - min;
            }
        }

        System.out.println(
             "Max profit is: " + maxProfit);
    }
}

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】问题 1431: 分糖果

问题描述 有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果,然后进行下面的游戏: 每个小朋友都把自己的糖果分一半给左手边的孩子。 一轮分糖后,...

662
来自专栏数据结构与算法

ABC108C - Triangular Relationship(打表)

给出$n, k$,求出满足$a+b, b + c, c + a$都是$k$的倍数的三元组$a, b, c$的个数,$1 \leqslant a, b, c \l...

411
来自专栏从零开始学自动化测试

python笔记1-用python解决小学生数学题

前几天有人在群里给小编出了个数学题: 假设你有无限数量的邮票,面值分别为6角,7角,8角,请问你最大的不可支付邮资是多少元? 小编掰着手指头和脚趾头算了下,答案...

2769
来自专栏Laoqi's Linux运维专列

if 条件语句

3498
来自专栏飞总聊IT

比特币和区块链(3):比特币的密码学知识之密码学哈希

其中主要原因是密码学知识在比特币的体系架构里扮演了非常重要的角色。接下来我们一起来了解下:密码学哈希

934
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:运算符

1446
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题5.8

题目描述 企业发放的奖金根据利润提成。利润低于或等于100000元的,奖金可提10%; 利润高于100000元,低于200000元(100000<I≤20000...

2587
来自专栏C语言C++游戏编程

C语言内置运算符丰富到令人头皮发麻,C语言基础教程之运算符篇

运算符是告诉编译器执行特定数学或逻辑函数的符号。C语言内置运算符丰富,并提供以下类型的运算符 -

1001
来自专栏数据结构与算法

牛客NOIP提高组(二)题解

好难啊,$30$分的枚举颜色dp应该比较好想把,$f[i][j]$表示第$i$个位置,填了$j$个颜色,然后先枚举一下$1$的颜色,前缀和优化一下,$O(n a...

491
来自专栏数据结构与算法

家庭问题

家庭问题 时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte 总提交 : 143  ...

3357

扫描关注云+社区