[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/

What Is Dynamic Programming With Python Examples

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. 

[Java/Python 3] Time O(n) space O(1) codes w/ brief explanation and a similar problem. - LeetCode Discuss