最大差值

[编程题]最大差值

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

输出

算法知识视频讲解

查看答案及解析

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)

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)