AOJ-ALDS1_1_D Maximum Profit【最值+水题】_海岛Blog的博客-程序员宅基地

技术标签： AOJ-ALDS1_1_D # ICPC-AOJ # ICPC水题之二 Maximum Profit # ICPC-序列处理

Maximum Profit

You can obtain profits from foreign exchange margin transactions. For example, if you buy 1000 dollar at a rate of 100 yen per dollar, and sell them at a rate of 108 yen per dollar, you can obtain (108 - 100) × 1000 = 8000 yen.

Write a program which reads values of a currency Rt at a certain time t (t=0,1,2,...n−1), and reports the maximum value of Rj−Ri where j>i .

Input

The first line contains an integer n. In the following n lines, Rt (t=0,1,2,...n−1) are given in order.

Output

Print the maximum value in a line.

Constraints

2≤n≤200,000
1≤Rt≤109

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

-1

问题链接：AOJ-ALDS1_1_D Maximum Profit

问题简述：

给定一组数，计算它们的最大差值。

问题分析：

本题的关键是设计一个时间复杂度为O(n)的算法。

如果简单地用暴力法来解就Out了！

最大差值有可能是负数，需要注意。

程序说明：

最大值的初值应该其变量类型的最小值，使用头文件limits.h中预先定义的值是一种好的选择。

题记：（略）

参考链接：（略）

AC的C++语言程序如下：

/* AOJ-ALDS1_1_D Maximum Profit */

#include <iostream>
#include <limits.h>

using namespace std;

const int N = 2e5;
int r[N];

int main()
{
    int n;

    cin >> n;
    for(int i=0; i<n; i++)
        cin >> r[i];

    int maxval = INT_MIN;
    int minval = r[0];
    for(int i=1; i<n; i++) {
        maxval = max(maxval, r[i] - minval);
        minval = min(minval, r[i]);
    }

    cout << maxval << endl;

    return 0;
}

本文链接：https://blog.csdn.net/tigerisland45/article/details/79336294

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

GJK碰撞检测（Matlab代码实现）_matlab 碰撞检测_荔枝科研社的博客-程序员宅基地

用形式化方法对算法进行验证是一种十分有效的手段，尤其是定理证明的方法用严格的数学公理和定理推理证明逻辑模型的性质，对所验证的性质而言是完备的，基于GJK算法设计了计算空间两条线段间距离的算法，用定理证明器HOL4对其相关的定义和定理进行形式化定义和证明，进而基于霍尔逻辑完成形式化表示和证明，对该算法的正确性实现了形式化验证。GJK是通过支持映射来计算空间中两个凸体间距的渐进算法，虽然其数学模型比较复杂,且难以理解,但是基于GJK模型的算法有快速，易实施且适用于多种凸体的优点。行百里者，半于九十。_matlab 碰撞检测

CSS 标签居中固定到底部_form-group固定布局在底部_天天上天庭的博客-程序员宅基地

style="position:fixed; bottom:0; right: 42%"在标签中加入这个样式就可以生效，样图<div class="form-group" style="position:fixed; bottom:0; right: 42%"> <div > <button class="btn btn-primary" type="submit">打印发票</button> .._form-group固定布局在底部

Nginx+Tomcat 动静分离实现负载均衡-程序员宅基地

0.前期准备使用Debian环境。安装Nginx(默认安装)，一个web项目，安装tomcat(默认安装)等。1.一份Nginx.conf配置文件Nginx+Tomcat 动静分离实现负载均衡Nginx+Tomcat 动静分离实现负载均衡基本配置这个文件，就可以实现负载了。但是里面的各种关系要了解就比较麻烦了。这篇博客，也不是教学篇，是记录一下，方便以后自己看了。2.基础讲解现在...

PCB设计——PCB设计中是否应该去除死铜？_敷铜要移除死铜吗-程序员宅基地

PCB死铜也叫PCB孤岛，是指在PCB中孤立无连接的铜箔，一般都是在铺铜时产生，那PCB设计中是否应该去除死铜呢？有人说应该去除，原因有三个：1、会造成EMI问题；2、增强搞干扰能力；3、死铜没什么用。　　但也有人说应该保留下来，原因有四个：1、去除会有大片空白，不美观；2、可以增加板子机械性能，避免出现受力不均弯曲的现象。　　小捷哥的看法是尽量去除死铜，原因如下：　　1、尽量..._敷铜要移除死铜吗

树莓派控制步进电机_树莓派驱动电机_SlowFeather的博客-程序员宅基地

树莓派控制步进电机前言设备连接源码前言测试步进电机设备名称型号树莓派3B+步进电机28BYJ-48-5V步进电机驱动板UL2003芯片驱动板连接步进电机插入驱动板驱动板VCC接树莓派5V驱动板GND接树莓派GND驱动板INA接树莓派20驱动板INB接树莓派26驱动板INC接树莓派16驱动板IND接树莓派19源码import RPi.GPIO as GPIOimport time#BCM 对应 GPIO numbers , BOARD _树莓派驱动电机

欢迎使用百度文库爬虫!你猜付费的能不能爬!_爬虫可以爬去百度文库付费的知识么-程序员宅基地

百度文库爬虫本程序可以通过网络爬虫实现对大部分百度文库资源的获取安装所需要的python库以下是爬虫需要用到的几个python库，需要提前安装好。不会安装或者安装失败的同学可以参考我另一篇博客1.beautifulsoup42. requests3. bs4源代码import requestsfrom bs4 import BeautifulSoupurl = 'https://wenku.baidu.com/view/cff4b11fe418964bcf84b9d528e_爬虫可以爬去百度文库付费的知识么