# leetcode 2016. Maximum Difference Between Increasing Elements（python）

2022-01-31 11:19:21

「 This is my participation 11 The fourth of the yuegengwen challenge 12 God , Check out the activity details ：2021 One last more challenge

### describe

Given a 0-indexed integer array nums of size n, find the maximum difference between nums[i] and nums[j] (i.e., nums[j] - nums[i]), such that 0 <= i < j < n and nums[i] < nums[j].

Return the maximum difference. If no such i and j exists, return -1.

Example 1:

``````Input: nums = [7,1,5,4]
Output: 4
Explanation:
The maximum difference occurs with i = 1 and j = 2, nums[j] - nums[i] = 5 - 1 = 4.
Note that with i = 1 and j = 0, the difference nums[j] - nums[i] = 7 - 1 = 6, but i > j, so it is not valid.
Copy code ``````

Example 2:

``````Input: nums = [9,4,3,2]
Output: -1
Explanation:
There is no i and j such that i < j and nums[i] < nums[j].
Copy code ``````

Example 3:

``````Input: nums = [1,5,2,10]
Output: 9
Explanation:
The maximum difference occurs with i = 0 and j = 3, nums[j] - nums[i] = 10 - 1 = 9.
Copy code ``````

Note:

• n == nums.length
• 2 <= n <= 1000
• 1 <= nums[i] <= 10^9

### analysis

According to the meaning , Give an example from 0 The start index length is n A list of nums , find nums[j] - nums[i] Maximum difference between , And 0 <= i < j < n , And nums[i] < nums[j] . If there is a maximum difference, return , Otherwise return to -1 .

The simplest way is the double cycle of violence ：

• Initialization result result by -1
• Traverse range(len(nums)-1) Every element in i , Re traversal range(i+1, len(nums)) Every element in j , If nums[j] <= nums[i] Then continue to the next cycle , Otherwise, use result Record nums[j]-nums[i] The maximum of
• Return after traversal result

``````class Solution(object):
def maximumDifference(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = -1
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if nums[j] <= nums[i]:
continue
result = max( result , nums[j]- nums[i])
return result

Copy code ``````

### Running results

``````Runtime: 316 ms, faster than 16.50% of Python online submissions for Maximum Difference Between Increasing Elements.
Memory Usage: 13.6 MB, less than 20.57% of Python online submissions for Maximum Difference Between Increasing Elements.
Copy code ``````

### analysis

You can also traverse once to find the maximum difference ,, Ideas ：

• Initialization result result by -1 ,minNum by nums[0] Indicates the current minimum value
• Start with the second element , Each element traversed from left to right , If nums[i] Greater than the current minimum minNum , Is executed max(result, nums[i]-minNum) to update result , And then execute min(minNum, nums[i]) Update the current minimum minNum
• Return after traversal result that will do

``````class Solution(object):
def maximumDifference(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = -1
minNum = nums[0]
for i in range(1, len(nums)):
if nums[i]>minNum:
result = max(result, nums[i]-minNum)
minNum = min(minNum, nums[i])
return result
Copy code ``````

### Running results

``````Runtime: 36 ms, faster than 60.29% of Python online submissions for Maximum Difference Between Increasing Elements.
Memory Usage: 13.6 MB, less than 20.57% of Python online submissions for Maximum Difference Between Increasing Elements.
Copy code ``````