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

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#开发者

深入abstract class和interface

abstract class和interface是Java语言中对于抽象类定义进行支持的两种机制,正是由于这两种机制的存在,才赋予了Java强大的面向对象能力。...

3539
来自专栏好好学java的技术栈

小海聊数据结构系列之早操排队图解冒泡排序

一直想写一些简单易懂的文章,因为平时看的很多的书籍或者文章都是看着很难受的感觉,当然,这并不是说书籍写的不好,只是说对于一些没有太多基础或者基础不是很好的来说,...

913
来自专栏非著名程序员

为什么要使用String

最近在培训课期间指导初学者。任务之一就是要大家完成一个类,要求这个类对key为String类型的map执行dwarwle操作。其中一位学员完成的类中,有如下方法...

18310
来自专栏落花落雨不落叶

一个比较有意思的C语言问题

2957
来自专栏海天一树

小朋友学C++(2):面向过程与面向对象

先用C++编写一个加法程序 #include <iostream> using namespace std; int add(int a, int b) { ...

3349
来自专栏Java技术栈

国外大神总结的 10 个 Java 编程技巧!

2262
来自专栏数说工作室

提取文本数据,分析师小王初上手!| 【SAS Says·扩展篇】正则表达式

文本分析很有用,数说君自己也玩过,炒鸡有意思,从论坛、网页上爬取网友的舆情数据,然后整理、统计、画图,就可以知道舆论的风暴是什么,可以知道网友最热议的话题、最想...

3896
来自专栏小樱的经验随笔

hihoCoder #1078 : 线段树的区间修改(线段树区间更新板子题)

#1078 : 线段树的区间修改 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 对于小Ho表现出的对线段树的理解,小Hi表示挺满...

2694
来自专栏我是攻城师

偏执却管用的10条Java编程技巧

3407
来自专栏java一日一条

由字符串反转(使用递归)引申出来一道Java面试题

在Java中,最好的实现就是用JDK中StringBuffer的反转方法,它不仅速度快,效率高,而且还知道如何处理unicode代理对(surrogate p...

671

扫码关注云+社区