求最大差值-在线编程-K6K4.com

给定一个数组arr，length(arr)>2，任取两个数arr[i]和arr[j], 其中：i<j，求max(arr[i]-arr[j]) 
要求：时间复杂度为O(n)

输入、输出描述

输入：

arr: 长度至少为2的整数数组
n: 数组长度

输出：

max(a[i]-a[j]) ,其中i

Example

输入：

arr: [1,3,7,2,5]
n: 5

输出：

代码：

import java.util.*;
 
public class Main {
 
    public int solution(int[] arr, int n) {
        int[] dp = new int[arr.length];
        int max = Math.max(arr[0], arr[1]);
        dp[0] = 0;
        dp[1] = arr[0] - arr[1];
        for (int i = 2; i < arr.length; i++) {
            boolean flag = false;
            if (arr[i] > max) {
                max = arr[i];
                flag = true;
            }
            if (!flag)
                dp[i] = Math.max(max - arr[i], dp[i - 1]);
            else
                dp[i] = dp[i - 1];
        }
        return dp[arr.length - 1];
    }
}