Test Message

c435: MAX ! MAX ! MAX !

內容

現在有 n 個數字，Bert 現在想要找兩個數字，i 跟 j ( i < j )

使 a[ i ] - a[ j ] 儘量大，請你寫個程式幫幫他~~

輸入

第一行有個數字 n (2 <= n <= 100000) 代表現在有 n 個數字~~

接下來一行 a[1] , a[2] …. , a[n]

(1 <= a[i] <= 100000)

2018.03.07 更新

5
5 4 3 2 1

輸出

請輸出一個數字 ans = max( a[ i ] - a[ j ] | i < j )

( i 必須小於 j )

4

解題思路

先整理出規則

  1. 因為 i < j ，較大值無法跟在其右邊的較小值組合

  2. 當出現一個比前面較大值(n)更大的值(m)後，m 後面所有較小值相對於 n，和 m 的差距一定更大。

所以目標就是遇到新的較大值後，將前面的最大差給記錄起來，然後將較大值設為新的較大值，如此反覆值到陣列結束。

完整程式碼

AC (11ms, 104KB)
#include <stdio.h>

int main()
{
    int n, max, min, tmp, best;
    while (scanf(" %d", &n) == 1)
    {
        scanf(" %d", &min);
        best = 0, max = min;
        while (--n)
        {
            scanf(" %d", &tmp);
            if (tmp < min)
                min = tmp;
            else if (tmp > max)
            {
                if (max - min > best)
                    best = max - min;
                max = min = tmp;
            }
        }
        printf("%d\n", best < max - min ? max - min : best);
    }
    return 0;
}