首页 > 试题广场 >

最大差值

[编程题]最大差值

热度指数：13693 时间限制：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

输出

算法知识视频讲解

C++

牛客472102317号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param n int整型 
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        // write code here
        int min_pos=0,res=0;
        for(int i=0;i<n;i++){
            if(A[i]<=A[min_pos])
                min_pos=i;
            else
                res=max(res,A[i]-A[min_pos]);
        }
        return res;
    }
};

发表于 2021-12-01 18:18:56 回复(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

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)

牛客665672417号

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A int整型一维数组 
 * @param ALen int A数组长度
 * @param n int整型 
 * @return int整型
 */
int getDis(int* A, int ALen, int n ) {
    // write code here
    int max=0;
    int sum=0;
    for(int i=0;i<ALen;i++)
    {
        for(int j=0;j<i;j++)
        {
            sum=0;
            sum=A[i]-A[j];
            if(sum>max)
            {
                max=sum;
            }
        }
    }
    return max;
}

可惜运行超时

发表于 2022-09-17 16:51:35 回复(0)

布加迪.威龙

static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}
();

class Solution {
  public:
    int getDis(vector<int>& A, int n) {
        int d[n];
        d[0] = A[0];
        int r = 0;
        for (int i = 1; i < n; ++i) {
            if (A[i] < d[i - 1])
                d[i] = A[i];
            else d[i] = d[i - 1];
        }
        for (int i = 1; i < n; ++i) {
            if (A[i] - d[i] > r)
                r = A[i] - d[i];
        }
        return r;
    }
};

发表于 2022-07-19 09:10:25 回复(0)

C++

hrdate

int getDis(vector<int>& A, int n) {
        // write code here
        int ans = 0, res = A[0];
        for(int i = 0; i < n; ++i) {
            res = min(res, A[i]);
            ans = max(ans,A[i] - res);
        }
        return ans;
    }

发表于 2022-03-05 20:48:46 回复(0)

C++

牛客嗷嗷

class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param n int整型 
     * @return int整型
     */
    int getDis(vector<int> &A, int n)
    {
        // write code here
        int max = 0, min = A[0];
        for (int i = 1; i < n; i++)
        {
            if (min > A[i])
            {
                min = A[i];
                continue;
            }
            int t = A[i] - min;
            max = (max > t ? max : t);
        }
        return max;
    }
};

发表于 2022-01-28 17:17:46 回复(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)

牛客940938163号

发表于 2024-10-29 00:20:56 回复(0)

terirx

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A int整型一维数组 
 * @param ALen int A数组长度
 * @param n int整型 
 * @return int整型
 */
int getDis(int* A, int ALen, int n ) {
    int max=0,temp=A[0];
    for(int i=0; i<ALen; i++)
    {
        max=max>(A[i]-temp)?max:(A[i]-temp);
        temp=A[i]>temp?temp:A[i];
    }
    return max;
    // write code here
}

发表于 2024-07-29 20:58:39 回复(0)

Python3

liangzhengjie

不断更新最小值，遇到比最小值大则取一次值就好了

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A int整型一维数组 
# @param n int整型 
# @return int整型
#
class Solution:
    def getDis(self , A: List[int], n: int) -> int:
        # write code here
        dp = [0 for i in range(n)]
        min_num = A[0]
    
        res = 0
        for i in range(1, n):
            min_num = min(min_num, A[i-1])

            if A[i] > min_num:
                res = max(res, A[i]- min_num)

        return res

编辑于 2024-03-19 22:38:53 回复(0)

贪吃的小鱼干蚌埠住了

最后也只能通过30个样例

int getDis(int* A, int ALen, int n ) {

// write code here

long long int min=A[0];

long long int max=0;

int i=0;

int j=0;

for(i=0;i<ALen-1;i++)

{

for(j=i;j<ALen;j++)

{

if((A[j]-A[i])>max)

{

max=(A[j]-A[i]);

}

return max;

}

发表于 2023-12-08 23:56:31 回复(0)

在刷代码的芝士很聪明

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型vector
     * @param n int整型
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        int k = A[0], max = 0;
        for (int i = 1; i < n; i++) {
            k = min(A[i], k);
            int p = A[i] - k;
            if (p > max)max = p;
        }
        return max;
    }  // write code here
};

发表于 2023-08-28 11:35:41 回复(0)

牛客931188754号

class Solution:

def getDis(self , A: List[int], n: int) -> int:

# write code here

min=A[0]

max=A[0]

req = 0

minindex = 0

maxindex = 0

for i in range(n):

if A[i] > max:

max = A[i]

maxindex = i

if A[i] < min:

if req < max - min:

req = max - min

max = A[i]

maxindex = i

min = A[i]

minindex = i

if maxindex > minindex:

if req < A[maxindex] - A[minindex]:

req = A[maxindex] - A[minindex]

return req

发表于 2023-05-27 14:13:13 回复(1)

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)

Python3

danspace

class Solution:
    def getDis(self , A: List[int], n: int) -> int:
        # write code here
        # dp[i]为到i点的最优解
        dp = [0]*n
        cur_min = A[0]
        for i in range(1, n):
            cur_min = min(cur_min, A[i])
            if A[i] <= A[i-1]:
                dp[i] = dp[i-1]
            else:
                dp[i] = max(dp[i-1], A[i] - cur_min)
        return dp[-1]

发表于 2023-04-27 13:53:48 回复(0)

牛客693279660号

func getDis(A []int, n int) int {
	// write code here
    //递归思想，类似动态规划
    //A[:n]最大差值 = Biggest{ A[n-1]-Smallest(A[:n]) , A[:n-1]最大差值 }
	results := 0        
	preSmallest := A[0] 
	for i := 1; i < n; i++ {
		v1 := A[i] - preSmallest
		v2 := results
		if v1 >= v2 {
			results = v1
		} else {
			results = v2
		}
		if preSmallest > A[i] {
			preSmallest = A[i]
		}
	}
	return results
}

发表于 2023-04-26 19:26:59 回复(0)

C++

hacks

用贪心过的

更新最小被减数和差值最大。

#include <climits>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型vector
     * @param n int整型
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        // write code here
        // 这个题目注意 要满足
        // 索引 b >=a   样例1 A[1]-A[0] =-4 ,A[1]-A[1] = 0

       // 找一个最小的被减数
       int cur = A[0] ; 
       int maxx = INT_MIN ; 
       for(int i = 0;i<n ; i++) {
            int diff = A[i] -cur ; 
            // 更新被减数
            // 在0-i
            cur = min (cur ,A[i]) ; 
            
            maxx = max(maxx,diff) ; 
       }
       return maxx ; 
    }
};
// [2676 4662 8383 357 6595 ] 5
// 6238
/**
 int maxx = INT_MIN ;
        // 枚举b
        for (int i = 0 ; i < n ; i++ ) {
            // 枚举a
            for (int j = 0 ; j < n ; j++ ) {
                if (A[i] - A[j] > maxx && i >=j) {
                    maxx = A[i] - A[j] ;
                }
            }


        }

*/

发表于 2023-03-23 23:59:04 回复(0)

在写日记的大师兄很想喝咖啡

class Solution:
    def getDis(self , A: List[int], n: int) -> int:
        ans = 0
        min = A[0]
        for i in A:
            if i < min:
                min = i
            if i - min > ans:
                ans = i - min
        return ans

发表于 2023-03-19 18:23:29 回复(0)

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A int整型一维数组 
 * @param n int整型 
 * @return int整型
*/
func getDis( A []int ,  n int ) int {
    ans:=0
    min:=A[0]
    for i:=1;i<n;i++{
        if A[i]<min{
            min=A[i]
        }
        if A[i]-min>ans{
            ans=A[i]-min
        }
    }
    return ans
}

发表于 2023-03-06 21:21:33 回复(0)