《寻衅步伐筹划比赛2 算法和数据布局》第二章实现

该文章为《寻衅步伐筹划比赛2 算法和数据布局》第二章的题解条记，该书告急借助AizuOnlineJudge（以下简称AOJ）上的课程题举行解说。

 ALDS1_1_D  Maximum Profit（最大利润）

---

目次
 ALDS1_1_D  Maximum Profit（最大利润）
标题形貌（图片内容为机翻）
代码实现
题解条记
总评
注意点
重点表明

---

标题形貌（图片内容为机翻）

代码实现

1. import java.util.Scanner;
3. public class Main {
4.     public static void main(String[] args) {
5.         int max, min, max_x;
6.         Scanner sc = new Scanner(System.in);
7.         int n = sc.nextInt();
8.         int a[] = new int[n];
9.         for (int i = 0; i < n; i++) {
10.             a[i] = sc.nextInt();
11.         }
12.         max = a[n - 1];
13.         min = a[0];
14.         max_x = max - min;
15.         for (int j = 1; j < n; j++) {
16.             max_x = Math.max(a[j] - min, max_x);
17.             min = Math.min(min, a[j]);
18.         }
19.         System.out.println(max_x);
20.         sc.close();
21.     }
22. }

复制代码

题解条记

总评

标题难度不大，但要求较多，有点绕，需细致思索。
该题重点在于找出局部的最大值和最小值，按照标题要求最大的代价差即极大值-极小值（不肯定为最大值-最小值），必要从局部观察，不能直接按团体找。
注意点

• 输出有次序要求的代价差的最大值，必要反面的数减去前面的数。次序很告急，不是单纯找出整个数列的最大值、最小值作差。
  
• 注意递减的环境，找最大值和最小值时间要注意端点，最大值不能为第一个数，最小值不能为末了一个数。
  
• 该题要有局部观，不能从团体来看，不要直接从前以后找出最小值后再找出该值反面的最大值，或从后往前先找出最大值后再找该值前面的最小值，要算出每个局部代价差的最大值。
  

重点表明

从前以后，找出局部的最大代价差，而且更新停止当前的最小值，即找到当前的极小值点，盘算出代价差（a[j]-min）后，与之前的最大代价差比力（max_x），末了更新最大代价差。