The O(n) Club: Longest Arithmetic Subsequence: Now With 99% Less Guessing

The O(n) Club: Longest Arithmetic Subsequence—Now With 99% Less Guessing

⚡ TL;DR

Find the longest arithmetic subsequence (LAS) in an array using dynamic programming—and don’t even think about brute force unless you have a decade to spare. Java makes it tidy:

// Quick DP teaser
int n = nums.length;
int[][] dp = new int[n][1001]; // 500 offset handles negatives
int max = 2;
for (int i = 0; i < n; i++)
  for (int j = 0; j < i; j++) {
    int diff = nums[i] - nums[j] + 500;
    dp[i][diff] = Math.max(dp[i][diff], dp[j][diff] + 1);
    max = Math.max(max, dp[i][diff]);
  }

🧠 How Devs Usually Mess This Up

• Substring confusion: No, it’s not a substring. Subsequence means you can skip numbers like you’re skipping chores.
• Forgetting negative/zero differences: Arithmetic means any difference, not just positive. Flat or falling? Still counts.
• The brute-force fan club: If you love 2ⁿ solutions, you’ve got bigger problems than this interview.

🔍 What’s Actually Going On

Think of party guests all doing the same goofy dance move—doesn’t matter who’s next to whom, as long as the pattern holds. Dynamic programming here tracks, for each possible (possibly gloomy) difference, the length of the train reaching each index. Negative difference? That’s the dance floor’s slippery slope, so we add an offset (Java arrays throw tantrums with negative numbers). Each potential diff gets its own scorecard.

🛠️ PseudoCode

• Loop over every index i in nums
  • At each i, look at every j < i
• Calculate diff = nums[i] - nums[j] (add 500 for array sanity)
• If you already have a subsequence ending at j with this diff, tack nums[i] on for one longer
• Otherwise, start new: minimum length for any pair is 2
• Update max each time like checking how many ugly sweaters showed up at this algorithmic party

💻 The Code

public int longestArithSeqLength(int[] nums) {
    int n = nums.length;
    if (n <= 2) return n;
    int[][] dp = new int[n][1001]; // covers [-500,500] differences
    int maxLen = 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j] + 500;
            dp[i][diff] = Math.max(dp[i][diff], (dp[j][diff] > 0 ? dp[j][diff] : 1) + 1);
            maxLen = Math.max(maxLen, dp[i][diff]);
        }
    }
    return maxLen;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Flat arrays: All elements the same? Still arithmetic, champ. LAS equals full array length.
• Negative differences: Math is cruel—subtract both ways, offset appropriately.
• Duplicate values galore: If a number repeats, count every sequence it fits. Don’t shortchange yourself.
• Space matters: O(n²) arrays survive here since diffs are capped, but for wild input, HashMap[] saves memory like a squirrel hoards nuts.

🧠 Interviewer Brain-Tattoo

If they ask for a subsequence, don’t chain yourself to adjacency. Skip, hop, and—above all—track every possible difference. That’s how you LAS-t longer.