📈Best Time to Buy and Sell Stock

Pattern: Siding Window

Idea: Keep track of best price so far and the maximum profit so far.

---

💻 Code

def maxProfit(prices: List[int]) -> int:

        ans = 0

        buy = 1e9

        for price in prices:

            if price>buy:

                ans = max(ans,price-buy)

            elif price<buy:

                buy = price

        return ans

Valley and Peak approach - Valley Peak approach

🔗References

Leetcode

🏢 Companies

Amazon, Google, Microsoft, Facebook, Apple, Adobe, Bloomberg, Uber, Oracle, Goldman Sachs, Salesforce, ByteDance, tiktok, Cisco, VMware, Expedia, Walmart Global Tech, Atlassian, Visa, eBay, JPMorgan, Paypal, Capital One, ServiceNow, Zoho, tcs, Docusign, Zoom, Netflix, Alation

---

This problem is 1D DP

Yes, it is both. Your code is a Dynamic Programming (DP) algorithm that adapts the exact core philosophy of Kadane’s Algorithm. [1, 2, 3]

Kadane’s algorithm itself is just a highly optimized, one-pass variation of Dynamic Programming. [4, 5]

Here is exactly how they connect to your code.

---

🗺️ The Hierarchy: How They Fit Together

   [ Dynamic Programming ]  <-- The broad problem-solving framework
              │
     [ Kadane's Algorithm ]  <-- A specific one-pass DP technique for optimization
              │
       [ Your Code ]        <-- Kadane's logic adapted for stock trading

---

🧠 How Kadane’s Logic Translates to Your Code

Kadane’s original algorithm finds the Maximum Subarray Sum by tracking two states at every step. Look at how perfectly your stock code mirrors that exact math: [6, 7, 8]

Feature	Standard Kadane’s (Max Subarray)	Your Stock Code
Local State	current_sum (Best sum ending here)	buy (Best price seen up to here)
Global State	max_sum (Best sum found anywhere)	ans (Best profit found anywhere)
The Choice	Should I extend the existing subarray or start a new one?	Should I sell at today’s price or use today’s price as a new buying floor?

---

🛠️ The Formal DP Proof (State Transitions)

To prove this is Dynamic Programming, we can express your code as formal DP State Transitions.

At any day $i$, the algorithm computes two historical states based purely on the previous day’s states ($i-1$): [9, 10, 11]

1. Buying State:
   $\text{buy}[i] = \min(\text{buy}[i-1], \text{price}[i])$
   (Memory of the lowest price up to day $i$)
2. Profit State:
   $\text{ans}[i] = \max(\text{ans}[i-1], \text{price}[i] - \text{buy}[i])$
   (Memory of the highest profit up to day $i$) [12]

Because you are using the optimal solutions of smaller subproblems (days $0$ to $i-1$) to solve the current subproblem (day $i$), it is a textbook Space-Optimized Bottom-Up Dynamic Programming solution. [13]

---