我要招人

去企业版

首页 > 试题广场 >

最大差值

[编程题]最大差值

热度指数：12312 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个长为 n 的数组 A ，求满足 0 ≤ a ≤ b < n 的 A[b] - A[a] 的最大值。

给定数组 A 及它的大小 n ，请返回最大差值。

数据范围： $2 < n \le 2*10^5\$ ，数组中的值满足 $0 \le |val| \le 5*10^8 \$

示例1

输入

[5,1],2

输出

示例2

输入

[5,6],2

输出

算法知识视频讲解

Java

梁山教父

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 max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            min=Math.min(A[i],min);
            if(A[i]-min>max){
                max=A[i]-min;
            }
        }
        return max;
    }
}

发表于 2023-05-18 15:39:06 回复(0)

Java

格调m

就是力扣上买卖股票最大值问题，只需要维护一个最小值，后面每个大于最小值的数减去这个最小值，求最大的就行

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 min = A[0], max = 0;
        for (int i = 1; i < n; i++){
            if (A[i] <= min){
                min = A[i];
            }else{
                max = Math.max(max, A[i] - min);
            }
        }
        return max;
    }
}

发表于 2022-07-21 21:35:38 回复(0)

Java

世界杯2009

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 min = A[0];
        int max = 0;
        for (int i = 1; i < n; i++) {
            max = Math.max(max, A[i] - min);
            min = Math.min(min, A[i]);
        }
        return max;
    }
}

发表于 2022-04-10 16:18:14 回复(0)

Java

整顿职场的外卷侠很年轻

public int getDis (int[] A, int n) {
    // write code here
    int min = A[0]; // 前i个数中的最小值
    // dp[i]：前i个数的最大差值
    int[] dp = new int[n];
    for(int i = 1; i < n; i++){
        min = Math.min(A[i], min);
        // 获取前i个数的最大差值
        dp[i] = Math.max(A[i] - min, dp[i - 1]);
    }

    return dp[n - 1];
}

发表于 2022-03-11 11:28:06 回复(0)

Java

马老师的金轮

 public int getDis (int[] A, int n) {
        // write code here
        int max = 0;
        int maxNum = Integer.MIN_VALUE;
        for(int i=n-1;i>=0;i--){
            if(A[i] > maxNum){
                maxNum = A[i];
            }
            if(maxNum - A[i] > max){
                max = maxNum - A[i];
            }
        }
        return max;
    }

发表于 2022-02-22 18:31:57 回复(0)

Java

牛客564955183号

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 temp = A[0], max = 0;
        for(int i = 1; i < n; ++i) {
            if(temp - A[i] < 0) {
                max = Math.min(max, temp - A[i]);
            } else {
                temp = A[i];
            }
        }
        return -max;
    }
}

发表于 2022-02-17 17:51:25 回复(0)

Java

老农爱编程

public int getDis (int[] A, int n) {
        // write code here
        int dp[] = new int[n]; // 存储最小值
        int max = 0;
        dp[0] = A[0]; //默认最小值
        for(int i = 1 ; i < n; i ++){
            dp[i] = Math.min(A[i],dp[i - 1]);
            max = Math.max(A[i] - dp[i],max);
        }
        return max;
    }

发表于 2022-01-14 10:33:31 回复(0)

Java

wanbf

int res = 0;
int min =A[0];//获得最小数
for(int i=1;i<n;i++){
if(A[i]<min){
min=A[i];
}else
res = Math.max(res,A[i]-min);
}
return res;

发表于 2022-01-08 18:08:20 回复(0)

Java

pein531

算法流程

使用预处理技巧，构建两个与原数组相同的辅助数组left和right：

left[i]表示包括A[i]在内的，及其左边所有元素中的最小值；
right[i]表示包括A[i]在内的，及其右边所有元素中的最大值。

然后遍历0~n，计算right[i]-left[i]的最大值即可

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[] left = new int[n], right = new int[n];
        left[0] = A[0];
        right[n - 1] = A[n - 1];
        for(int i = 1; i < n; i++){
            left[i] = Math.min(left[i - 1], A[i]);
            right[n - 1 - i] = Math.max(A[n - 1 - i], right[n - i]);
        }
        int maxDiff = 0;
        for(int i = 0; i < n; i++){
            maxDiff = Math.max(maxDiff, right[i] - left[i]);
        }
        return maxDiff;
    }
}

复杂度分析
left数组和right数组可以通过遍历一遍求得，时间复杂度为O(n)。然后求最大差值再遍历一遍，时间复杂度为O(n)，算法整体的复杂度还是O(n)。而开辟了两个辅助数组的空间，空间复杂度为O(n)。

发表于 2021-12-15 14:29:27 回复(0)

Java

啊哈哈h

import java.util.*;
public class Solution {
    public int getDis (int[] A, int n) {
        int min = A[0];
        int[] dp = new int[n];
        dp[0] = A[0];
        int res = 0;
        for(int i = 1; i < n; i++){
            min = Math.min(min, A[i]);
            dp[i] = A[i] - min;
            res = Math.max(dp[i], res);
        }
        return res;
    }
}

发表于 2021-12-01 13:18:00 回复(0)