题解 | #最大差值#

思路：动态规划，dp[i]记录当前A[i]的最大差值
dp[i] = Max(dp[i-1],A[i]-Min(A[0],...A[n-1]))
最后返回dp数组的最后一个值即可

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型一维数组
     * @param n int整型
     * @return int整型
     */
    public int getDis (int[] A, int n) {
        // write code here
        int length = A.length;
//        保存最大差值
        int[] dp = new int[length];
        dp[0] = 0;
        int min = A[0];
        for (int i = 1; i < length; i++) {
            dp[i] = Math.max(dp[i - 1], A[i] - min);
            if (A[i] < min) {
                min = A[i];
            }
        }
        return dp[length - 1];
    }
}