leetcode 题解 | 121. 买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。    
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路:

很简单的题目~

保存最小的值,在遍历过程中寻找与这个最小值差值最大的元素。

遍历的过程中保存最大的差值。

源代码:GCC 0ms

#include <stdlib.h>
#include <string.h>

#define printf //printf

//最大利润计算
int maxProfit(int* prices, int pricesSize) {
    int min = -1;
    int max = 0;

    for(int i=0; i<pricesSize; ++i){
        //寻找最小的元素
        if(min == -1 || min > prices[i]){
            //更新最小的元素
            min = prices[i];
            printf("min:%d\n", min);
        }
        //当前元素与最小的比较
        if(prices[i] - min > max){
            //更新max值
            max = prices[i] - min;
            printf("max:%d\n", min);
        }
    }

    return max;
}

int main()
{
    int prices[6] = {7,1,5,3,6,4};
    printf("%d\n", maxProfit(prices, 6));
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-07-10

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-202-Happy Number

3177
来自专栏HansBug's Lab

1935: [Shoi2007]Tree 园丁的烦恼

1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

2948
来自专栏chenjx85的技术专栏

leetcode-860-柠檬水找零

1274
来自专栏算法修养

HYSBZ 2160 拉拉队排练(回文树)

2160: 拉拉队排练 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 825  Solved: 324 [...

3387
来自专栏专注研发

poj-1008-玛雅历

上周末,M.A. Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳(玛雅人用于记事的工具)中,教授发现玛雅人使用了一个一年有365天的叫做Haab的历法...

1653
来自专栏james大数据架构

算法系列

  算法对程序员来说是熟悉的陌生人,编过大量代码后突然被哪个问到算法是什么也有时不知从何说起,简单来说是没有好好总结过仔细分析过。大学里面导师整天苦口婆心的教导...

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

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

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

852
来自专栏swag code

荷兰国旗-快排应用

”荷兰国旗难题“是计算机科学中的一个程序难题,它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。

892
来自专栏落影的专栏

程序员进阶之算法练习(三十一)

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。

1463
来自专栏斑斓

编码 | 并非Null Object这么简单

在大多数程序语言中,我们都需要与Null打交道,并且纠缠于对它的检查中。一不小心让它给溜出来,就可能像打开潘多拉的盒子一般,给程序世界带来灾难。说起来,在我们人...

3397

扫码关注云+社区