Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Longest Alternating Subsequence

Problem Statement

Given a number sequence, find the length of its Longest Alternating Subsequence (LAS). A subsequence is considered alternating if its elements are in alternating order.

A three element sequence (a1, a2, a3) will be an alternating sequence if its elements hold one of the following conditions:

{a1 > a2 < a3 } or { a1 < a2 > a3}.

Example 1:

Input: {1,2,3,4}
Output: 2
Explanation: There are many LAS: {1,2}, {3,4}, {1,3}, {1,4}

Example 2:

Input: {3,2,1,4}
Output: 3
Explanation: The LAS are {3,2,4} and {2,1,4}.

Example 3:

.....

.....

.....

Like the course? Get enrolled and start learning!
C

Cockles

· 4 years ago

typo in the memo top down solution the 2nd case should be isAsc

Show 1 reply
S

Seho Park

· 4 years ago

Would you add more explanations why {1,2,3,4} is 2? the given explanation is not enough to understand

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLASLength(self, nums):
    
    # DP array that stores LAS and index i and relation < or > between consecutive numbers 
    longest_alt = [(1, '.')] * len(nums) # . is an initial value 
    
    for i in range(1, len(nums)):
      if nums[i] < nums[i - 1]: # search for the > and take the LAS + 1
        for j in range(i - 1, - 1,  - 1):
          if longest_alt[j][1] == '>' or longest_alt[j][1] == '.':
            longest_alt[i] = (longest_alt[j][0] + 1, '<')
            break
      elif nums[i] > nums[i - 1]: # search for the < and take the LAS + 1
        for j in range(i - 1, - 1,  - 1):
          if longest_alt[j][1] == '<' or longest_alt[j][1] == '.':
            longest_alt[i] = (longest_alt[j][0] + 1, '>')
            break
      else: # clone