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

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 条评论
登录 后参与评论

相关文章

来自专栏专知

关关的刷题日记82 – Leetcode 453. Minimum Moves to Equal Array Elements

关关的刷题日记82 – Leetcode 453. Minimum Moves to Equal Array Elements 题目 Given a non-e...

2775
来自专栏mwangblog

python循环执行

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

P1403 [AHOI2005]约数研究

题目描述 科学家们在Samuel星球上的探险得到了丰富的能源储备,这使得空间站中大型计算机“Samuel II”的长时间运算成为了可能。由于在去年一年的辛苦工作...

3635
来自专栏专知

【关关的刷题日记64】Leetcode 110 Balanced Binary Tree

关关的刷题日记64 – Leetcode 110 Balanced Binary Tree 题目 Given a binary tree, determine ...

2687
来自专栏专知

关关的刷题日记98 – Leetcode 106. Construct Binary Tree from Inorder

关关的刷题日记98 – Leetcode 106. Construct Binary Tree from Inorder and Postorder Trave...

3436
来自专栏领域驱动设计DDD实战进阶

领域驱动设计之工厂

2565
来自专栏desperate633

LintCode 买卖股票的最佳时机题目分析代码

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

554
来自专栏Java后端生活

MySQL(四)DQL之条件查询

1489
来自专栏CDA数据分析师

就算不做数据分析师也要学会这8个IF函数

今天所讲的IF函数,包括excel中含有IF的系列函数,共有8个,每个函数列举最了常用的2~3个公式,希望能对同学们有用。 一、IF函数 作用:根据条件进行判断...

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

[每日一题]发工资咯

题目描述 作为程序猿,最盼望的日子就是每月的9号了,因为这一天是发工资的日子,养家糊口就靠它了,呵呵 但是对于公司财务处的工作人员来说,这一天则是很忙碌的一...

2738

扫码关注云+社区