1D Dynamic Programming Beyond the Basics: LIS, Max Product Subarray, and Word Break

You've climbed stairs and robbed houses. You know the DP framework — define state, write recurrence, handle base cases. Now let's use that muscle on problems where the state definition isn't handed to you.

Three problems. Three different shapes of 1D DP that show up constantly at mid-to-senior level interviews: Longest Increasing Subsequence, Maximum Product Subarray, and Word Break. Each one teaches you something the warmup problems didn't.

What Changes in "Real" 1D DP

The label "1D" means your DP state is a single array. But what that array stores varies a lot. In Climbing Stairs, dp[i] is the count of ways to reach step i — intuitive. LIS stores "the best answer ending at this position." Max Product tracks two values per position (max and min) because negatives flip signs. Word Break stores a boolean: "is this prefix reachable?"

Learning to ask "what's the most useful thing I could know if I were standing at position i?" is the skill that transfers. The recurrence usually falls out once you have that.

Problem 1: Longest Increasing Subsequence (LeetCode 300)

The problem: Given an integer array nums, return the length of the longest strictly increasing subsequence. Subsequence = elements in order, but not necessarily contiguous.

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4 — the subsequence [2, 3, 7, 101]

The State Definition

dp[i] = length of the longest increasing subsequence that ends at index i.

Every element starts with dp[i] = 1 (it's a valid subsequence of length 1 by itself). Then for each i, we look back at all j < i where nums[j] < nums[i] and see if we can extend any of those subsequences.

Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

Here's how dp fills in for [10, 9, 2, 5, 3, 7, 101, 18]:

Approach 1: Brute Force Recursion

// Brute force — O(2^n) time, O(n) space (call stack)
const lengthOfLIS = (nums) => {
  const lis = (i) => {
    let best = 1;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) {
        best = Math.max(best, 1 + lis(j));
      }
    }
    return best;
  };
 
  let result = 0;
  for (let i = 0; i < nums.length; i++) {
    result = Math.max(result, lis(i));
  }
  return result;
};

Exponential. Recomputes the same indices many times over.

Approach 2: DP — O(n²)

// DP — O(n²) time, O(n) space
const lengthOfLIS = (nums) => {
  const n = nums.length;
  if (n === 0) return 0; // without this, Math.max(...[]) below returns -Infinity
  const dp = new Array(n).fill(1);
 
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
 
  return Math.max(...dp);
};

This is the interview version. Clean, clear, and fast enough for the typical n ≤ 2500 constraint.

Approach 3: Binary Search — O(n log n)

The patience sort trick: maintain a tails array where tails[k] is the smallest tail element across all increasing subsequences of length k+1. For each new number, binary search to find where it belongs.

// O(n log n) time, O(n) space
const lengthOfLIS = (nums) => {
  const tails = [];
 
  for (const num of nums) {
    let lo = 0, hi = tails.length;
 
    // Find leftmost position where tails[pos] >= num
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
 
    tails[lo] = num; // Replace existing or append
  }
 
  return tails.length;
};

The tails array is not a valid LIS — it's a bookkeeping structure. Its length is the answer. For LeetCode 673 (number of LIS) or reconstructing the actual subsequence, you need extra tracking.

Problem 2: Maximum Product Subarray (LeetCode 152)

The problem: Find the contiguous subarray within nums that has the largest product. Return that product.

Input: [2, 3, -2, 4]
Output: 6 — subarray [2, 3]

The Twist

If all numbers were positive, Kadane's algorithm (with multiplication instead of addition) works perfectly. Negatives break this because a very large negative × another negative = a very large positive. So you can't just track the running max — you also need the running minimum, because the minimum today might become the maximum tomorrow.

At each position, the new max is the best of: starting fresh with num, extending the previous max, or extending the previous min (if both are negative).

Approach 1: Brute Force

// O(n²) time, O(1) space
const maxProduct = (nums) => {
  let result = nums[0];
 
  for (let i = 0; i < nums.length; i++) {
    let product = 1;
    for (let j = i; j < nums.length; j++) {
      product *= nums[j];
      result = Math.max(result, product);
    }
  }
 
  return result;
};

Approach 2: Optimized DP with Max and Min Tracking

// O(n) time, O(1) space
const maxProduct = (nums) => {
  let maxP = nums[0];
  let minP = nums[0];
  let result = nums[0];
 
  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];
    // Compute both candidates before assigning (avoids mutation bugs)
    const newMax = Math.max(num, maxP * num, minP * num);
    const newMin = Math.min(num, maxP * num, minP * num);
    maxP = newMax;
    minP = newMin;
    result = Math.max(result, maxP);
  }
 
  return result;
};

Trace through [2, 3, -2, 4]:

The key moment: at i=2, even though num=-2, we preserve minP=-12 because that negative could flip to a big positive next step. It doesn't here, but that's why the tracking matters.

Problem 3: Word Break (LeetCode 139)

The problem: Given string s and a dictionary wordDict, return true if s can be segmented into dictionary words.

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Thinking About Gaps, Not Characters

Imagine n+1 "positions" — one before the first character and one after each character. dp[i] means "can we validly segment the first i characters of s?" (i.e., can we reach position i?).

Base case: dp[0] = true — the empty prefix is trivially valid.

Transition: dp[i] = true if there exists j < i where dp[j] = true AND s[j..i-1] is in the dictionary.

Approach 1: Naive Recursion

// O(2^n) time without memoization, O(n) space
const wordBreak = (s, wordDict) => {
  const set = new Set(wordDict);
 
  const canBreak = (start) => {
    if (start === s.length) return true;
    for (let end = start + 1; end <= s.length; end++) {
      if (set.has(s.slice(start, end)) && canBreak(end)) {
        return true;
      }
    }
    return false;
  };
 
  return canBreak(0);
};

Approach 2: DP — O(n² · L) where L is average word length

// O(n² · L) time, O(n + dict_size) space
const wordBreak = (s, wordDict) => {
  const set = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
 
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break; // Found a valid split, no need to check further j's
      }
    }
  }
 
  return dp[n];
};

Approach 3: DP with Trie (for large dictionaries)

When the dictionary is huge and words are short, iterating all j < i per position is wasteful. A Trie lets you scan backward from each reachable position without redundant work.

// O(n²) time with faster constant factor, O(n + total_dict_chars) space
const wordBreak = (s, wordDict) => {
  // Build trie
  const trie = {};
  for (const word of wordDict) {
    let node = trie;
    for (const ch of word) {
      node[ch] ??= {};
      node = node[ch];
    }
    node.isWord = true; // End-of-word marker
  }
  // Note the marker key: child keys are always single characters, so `isWord` can never
  // collide with one. A single-character sentinel like '$' can — a dictionary containing
  // "a$" would make the trie report "a" as a complete word.
 
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
 
  for (let i = 0; i < n; i++) {
    if (!dp[i]) continue; // No path reaches position i
 
    let node = trie;
    for (let j = i; j < n; j++) {
      const ch = s[j];
      if (!node[ch]) break; // No word starts this way from position i
      node = node[ch];
      if (node.isWord) dp[j + 1] = true; // Found a complete word
    }
  }
 
  return dp[n];
};

The Trie version is overkill for most interview problems — bring it up as a follow-up if the interviewer asks about scaling to a dictionary with millions of entries.

Interview Tips

On LIS: The O(n²) solution is almost always sufficient given typical constraints. If you jump straight to the binary search solution without explaining the DP, you'll likely get follow-up questions you can't answer cleanly. Explain the DP first, then offer the O(n log n) as an optimization. Common follow-ups: "Can you reconstruct the actual subsequence?" (yes, with a prev pointer array) and "What's the number of LIS?" (LeetCode 673, harder).

On Max Product Subarray: Two gotchas interviewers love: "What if the array is all zeros?" (works fine — result stays 0) and "What if it's a single negative number?" (the answer is that number, which is handled by seeding with nums[0]). Also watch for the edge case where you compute newMax using the old minP before overwriting it — the code above handles this by computing both before assigning.

On Word Break: The follow-up is almost guaranteed to be Word Break II (LeetCode 140) — return all valid sentences instead of just a boolean. The DP logic is identical; you swap the boolean dp array for an array of string arrays. The big trap is that Word Break II can have exponentially many solutions (e.g., s = "aaaaa...", wordDict = ["a", "aa", "aaa", ...]), so memoization alone doesn't save you — pruning matters. Keep that in mind if the interviewer seems interested in complexity.

The meta-lesson: 1D DP problems look diverse on the surface, but they all come down to "what do I need to know at position i to make progress?" Once that question has a clean answer, the recurrence usually writes itself.