Skip to content

Longest Climbing Streak

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Longest Climbing Streak

A stock's daily prices are stored in nums. An analyst wants the length of the longest strictly increasing sequence of prices, where the chosen days need not be adjacent but must keep their order.

Return the length of the longest strictly increasing subsequence.

def length_of_lis(nums):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Dynamic Programming, Longest Increasing Subsequence, Arrays

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: Do the chosen days need to be consecutive in nums?
    • A: No. The subsequence can skip days, but the chosen prices must keep their original left-to-right order.
  • Q: Does "strictly increasing" allow equal prices?
    • A: No. Each chosen price must be strictly greater than the one before it, so repeated values cannot both be part of the streak.
  • Q: What should we return if nums contains only one price?
    • A: A single price is a valid streak of length 1.
HAPPY CASE
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest strictly increasing subsequence is [2, 3, 7, 101] (or [2, 5, 7, 101]), which has length 4.

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: The longest strictly increasing subsequence is [0, 1, 2, 3], which has length 4.

EDGE CASE
Input: nums = [7, 7, 7, 7]
Output: 1
Explanation: The streak must be strictly increasing, so equal prices cannot extend it. Any single day is the best we can do.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Longest Subsequence Problems, we can consider the following approaches:

  • Dynamic Programming: This is the classic Longest Increasing Subsequence (LIS) pattern. The answer for each index depends on the answers for earlier indices, so we can build a 1D DP table where dp[i] stores the length of the longest increasing subsequence ending at index i.
  • Binary Search (Patience Sorting): An optimized O(N log N) approach maintains a list of the smallest possible tail for each subsequence length, but the O(N^2) DP is the standard interview baseline.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Define dp[i] as the length of the longest strictly increasing subsequence that ends at index i. Every index starts at 1 (the day by itself). For each day i, look back at every earlier day j: if nums[j] < nums[i], then the streak ending at j can be extended by day i, so dp[i] can become dp[j] + 1. The final answer is the maximum value in the DP table, since the longest streak can end anywhere.

1) If nums is empty, return 0.
2) Initialize dp as a list of 1s, one entry per price (every day is a streak of length 1 by itself).
3) For each index i from 1 to n - 1:
   a) For each earlier index j from 0 to i - 1:
      i) If nums[j] < nums[i], the streak ending at j can be extended by nums[i]:
         dp[i] = max(dp[i], dp[j] + 1)
4) Return the maximum value in dp.

⚠️ Common Mistakes

  • Returning dp[n - 1] instead of max(dp) — the longest streak does not have to end on the last day.
  • Using nums[j] <= nums[i] instead of nums[j] < nums[i], which wrongly lets equal prices extend a strictly increasing streak.
  • Confusing subsequence with subarray and only counting consecutive days.
  • Forgetting to initialize every dp[i] to 1, which undercounts streaks that start at i.

4: I-mplement

Implement the code to solve the algorithm.

def length_of_lis(nums):
    if not nums:
        return 0

    n = len(nums)
    # dp[i] = length of the longest strictly increasing subsequence ending at index i
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            # If the price on day j is lower, day i can extend that streak
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    # The longest streak can end at any index
    return max(dp)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]

    • dp starts as [1, 1, 1, 1, 1, 1, 1, 1].
    • Day 5 (price 5) extends the streak ending at 2: dp = [1, 1, 1, 2, ...].
    • Day 7 (price 7) extends the streaks ending at 5 or 3: dp[5] = 3.
    • Day 101 extends the streak ending at 7: dp[6] = 4; day 18 also reaches dp[7] = 4.
    • Final dp = [1, 1, 1, 2, 2, 3, 4, 4].
    • Output: 4 (e.g. [2, 3, 7, 101])

  • Input: nums = [0, 1, 0, 3, 2, 3]

    • dp builds up as [1, 2, 1, 3, 3, 4]: price 3 at the last index extends the streak [0, 1, 2].
    • Output: 4 (the subsequence [0, 1, 2, 3])

  • Input: nums = [7, 7, 7, 7]

    • No price is strictly greater than an earlier one, so dp stays [1, 1, 1, 1].
    • Output: 1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of prices in nums.

  • Time Complexity: O(N^2) because for each index we scan all earlier indices to find streaks it can extend.
  • Space Complexity: O(N) for the DP table storing the best streak length ending at each index.

A follow-up optimization uses binary search over a list of smallest tail values (patience sorting) to bring the time down to O(N log N), at the cost of a less intuitive implementation.

Clone this wiki locally