[Leetcode] 2016. Maximum Difference Between Increasing Elements

[Leetcode] 2016. Maximum Difference Between Increasing Elements

Review of the Leetcode 2016. Maximum Difference Between Increasing Elements.

Below was my answer.

I approached this problem as getting difference using combination not breaking the rule of the order.

from itertools import combinations class Solution: def maximumDifference(self, nums: List[int]) -> int: ans = [] if nums.index(max(nums)) > nums.index(min(nums)): return max(nums)-min(nums) else: comb = combinations(nums, 2) for i in list(comb): if i[1]-i[0]>0: ans.append(i[1]-i[0]) else: ans.append(-1) return(max(ans))

However, there were more simple answers.

This user approached this problem with dynamic programming. Three stpes of dynamic programming is divide, conquer, and combine. Dividing the problem as sub-problems, solving sub-problems recursively, and then combine the solved sub-problems to make conclusion.

In here, we don't need any combinations like my answer. What we need to do is just remembering the results and compare next values saving bigger values for next comparison.

def maximumDifference(self, nums: List[int]) -> int: # -1: in case there are is no avaiable maximum difference. diff, mi = -1, math.inf for i, n in enumerate(nums): if i > 0 and n > mi: # compare previously calculated value and current one and save the bigger value diff = max(diff, n - mi) # save the min value mi = min(mi, n) return diff

Next time I confront the problems like above, I should try to solve the problem with dynamic programming.

[Reference]

https://skerritt.blog/dynamic-programming/

https://leetcode.com/problems/maximum-difference-between-increasing-elements/discuss/1486323/JavaPython-3-Time-O(n)-space-O(1)-codes-w-brief-explanation-and-a-similar-problem.

from http://jwon-yoon.tistory.com/24 by ccl(A) rewrite - 2021-10-26 04:02:22