有一个长为 n 的数组 A ,求满足 0 ≤ a ≤ b < n 的 A[b] - A[a] 的最大值。
给定数组 A 及它的大小 n ,请返回最大差值。
数据范围: ,数组中的值满足
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @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
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]