🧠 Solving LeetCode Until I Become Top 1% — Day `21`

🔹 Problem: 2016. Maximum Difference Between Increasing Elements

Difficulty: #Easy
Tags: #PrefixSum #KadanesAlgorithm

📝 Problem Summary (in your own words)

Given an array of integers, find the maximum difference between two elements such that the larger element comes after the smaller one in the array.

🧠 My Thought Process

Brute Force Idea:
We can use a nested loop to check every pair of elements, but this will be inefficient because the time complexity will be O(n^2).
Optimized Strategy:
Although the O(n^2) approach works, there is a more efficient way to solve this problem using a single pass through the array. Keep this pattern in mind if you encounter a problem where you need to din the maximum or minimum of a sequence of elements you can use [[prefix_sum]] algorithm. But there is a catch prefix sum is a modified version of another [[dp]] algorithm called [[kadane's_algorithm]].

"Kadene's algorithm keeps track of the past, only if it's valueable"

Key Insight:
- Maintain a variable to track the minimum value seen so far as you iterate through the array.
- For each element, calculate the difference between the current element and the minimum value.
- Update the maximum difference if this new difference is larger.
- Algorithm Used: [[kadane's_algorithm]]

⚙️ Code Implementation (Python)

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        res = -1
        mn = nums[0]


        for i in nums[1:]:
            if i > mn:
                res = max(res, i-mn)

            else:
                mn = i


        return res

⏱️ Time & Space Complexity

Time: O(n) — single pass through the array
Space: O(1) — only a few variables used

🧩 Key Takeaways

✅ What concept or trick did I learn?
- Kadane's Algorithm can be adapted to find maximum differences in sequences.
💡 What made this problem tricky?
- Recognizing that the problem can be solved in linear time rather than quadratic.
💭 How will I recognize a similar problem in the future?
- Look for problems that involve finding a result based on the relationship between elements in a sequence, especially keeping track of the previous minimum or maximum values.