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

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

相关文章

来自专栏张善友的专栏

Using sqlite with .NET

The other day I found that there is a .NET wrapper for sqlite. sqlite is a very ...

2288
来自专栏积累沉淀

Hive2.0.0操作HBase 1.2.1报错解决

首先看错  org.apache.hive.service.cli.HiveSQLException: Failed to open new session: ...

2339
来自专栏葡萄城控件技术团队

Table-values parameter(TVP)系列之二: 利用DataTable将其作为参数传给SP

一,回顾         上一部分讲述了“在T-SQL中创建和使用TVP”,通过T-SQL建立如下的对象:         1)Tables ...

2069
来自专栏玩转JavaEE

RestTemplate的逆袭之路,从发送请求到负载均衡

上篇文章我们详细的介绍了RestTemplate发送请求的问题,熟悉Spring的小伙伴可能会发现:RestTemplate不就是Spring提供的一个发送请求...

1.1K4
来自专栏C# 编程

C#使用DataSet类、DataTable类、DataRow类、OleDbConnection类、OleDbDataAdapter类编写简单数据库应用

//注意:请使用VS2010打开以下的源代码。 //源代码地址:http://pan.baidu.com/s/1j9WVR using System; usi...

2460
来自专栏跟着阿笨一起玩NET

[C#]工具类—FTP上传下载

  不错的文章:http://www.cnblogs.com/greatverve/archive/2012/03/03/csharp-ftp.html

1181
来自专栏菩提树下的杨过

SqlTransaction事务使用示例

using System; using System.Data; using System.Data.SqlClient; using System.Co...

1858
来自专栏跟着阿笨一起玩NET

C# 通过HttpWebRequest在后台对WebService进行调用

http://www.cnblogs.com/macroxu-1982/archive/2009/12/23/1630415.html

2782
来自专栏菩提树下的杨过

winform中linkLabel的用法(示例)

private void Form1_Load(object sender, EventArgs e)         {             this...

1925
来自专栏码匠的流水账

聊聊EurekaRibbonClientConfiguration

spring-cloud-netflix-eureka-client-2.0.0.RELEASE-sources.jar!/org/springframewor...

1171

扫码关注云+社区