Wiggle Subsequence
Finding the length of a longest wiggle subsequence is an interesting problem. We’ll solve it first using dynamic programming and then using a greedy algorithm. We’ll compare and contrast the two different approaches that we used to solve the problem towards the end of the article.
Problem Statement
A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.
- For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
- In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.
A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
Given an integer array nums, return the length of the longest wiggle subsequence of nums. [1]
Dynamic Programming Solution
We let $i$ be the current element and $j$ be the previous element in our wiggle subsequence: $j < i$. Let $lastIncLen[i]$ and $lastDecLen[i]$ be the length of the longest wiggle subsequence where $a_{j} \lt a_i$ and $a_{j} \gt a_i$ respectively. What follows is our recurrence.
$lastIncLen[i] = max_{\forall j: 0 \le j \lt i}(lastDecLen[j] + 1),\;\;\;$ if $nums[i] \gt nums[j].$
$lastDecLen[i] = max_{\forall j: 0 \le j \lt i}(lastIncLen[j] + 1), \;\;\;$ if $nums[i] \lt nums[j].$
The recurrence follows directly from the definition of the wiggle sequence. What follows is our pseudocode for the dynamic programming solution.
$\phantom{{}++{}}$ $n \gets nums.length$
$\phantom{{}++{}}$ let $lastIncLen$ and $lastDecLen$ be arrays of length $n$
$\phantom{{}++{}}$ $lastIncLen[1] = 1$
$\phantom{{}++{}}$ $lastDecLen[1] = 1$
$\phantom{{}++{}}$ int $l = 1$
$\phantom{{}++{}}$ `for` $i = 2$ to $n$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `for` $j = 1$ to $i - 1$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $nums[i] \gt nums[j]$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $lastIncLen[i] = max(lastIncLen[i], lastDecLen[j] + 1)$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `else if`
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $lastDecLen[i] = max(lastDecLen[i], lastIncLen[j] + 1)$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $l = max(l, max(lastIncLen[i], lastDecLen[i]))$
$\phantom{{}++{}}$ `return` $l$
Sample Implementation
Here’s the sample implementation along with a driver program for our dynamic programming solution described above.
Analysis
Our dynamic programming solution involves $O(n^2)$ asymptotic time complexity and $\Theta(n)$ space complexity.
Can we do better
The next question that comes to our mind is that is there any better way of doing this? The answer is yes. We’ll take a look at it next.
Greedy Approach
We let $a_1$ and $a_2$ be the first two elements in our wiggle subsequence. If we inspect carefully, there are just two ways to start the wiggle subsequence: $a_1 \lt a_2$ or $a_1 \gt a_2$. What if we try both and find the optimal solution $l1$ and $l2$ respectively. Let $i$ be the current element we inspect. If the previous step was increasing and the current step is decreasing: $a_{i-1} \gt a_i$, we then increment the length by 1. If the previous step was decreasing and the current step is increasing: $a_{i-1} \lt a_i$, then we increment length by 1. If there's an increasing or decreasing sequence of elements, we keep the largest or smallest element respectively, with the hope of getting a longer wiggle subsequence. This is our greedy choice property. [2]
Proof of correctness
Lemma 1.0
If there’s an increasing sequence, then we should consider the largest element.
Proof
Without the loss of generality, let’s assume that we have the elements $a_p \gt a_q \lt a_r \lt a_s \gt a_t$ such that $a_r \lt a_t$ as last five elements in our input sequence. Assume that choosing $a_r$ gives us an optimal solution. If $a_r$ is chosen, we get a longest wiggle subsequence of length $l$. However, if we choose $a_s$, then we get a wiggle subsequence of length $l + 1$. A contradiction. Thus, proving our claim. [2]
The proof for a decreasing sequence is symmetric to this.
Theorem 1.0
Procedure $WIGGLE\_MAX\_LEN$ produces the length of a longest wiggle subsequence.
Proof
Immediate from Lemma 1.0.
Now let’s write the pseudocode for the greedy approach.
$\phantom{{}++{}}$ $l1 \gets WIGGLE\_LEN(nums, true)$
$\phantom{{}++{}}$ $l2 \gets WIGGLE\_LEN(nums, false)$
$\phantom{{}++{}}$ `return` $max(l_1, l_2)$
WIGGLE_LEN(nums, increasing)
$\phantom{{}++{}}$ $n \gets nums.length$
$\phantom{{}++{}}$ $inc \gets increasing$
$\phantom{{}++{}}$ $l \gets 1$
$\phantom{{}++{}}$ `for` $i = 2$ to $n$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $inc\;$ and $\;nums[i] \lt nums[i - 1]$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $l \gets l + 1$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $inc \gets false$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `else if` $!inc\;$ and $\;nums[i] > nums[i - 1]$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $l \gets l + 1$
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $inc \gets true$
$\phantom{{}++{}}$ `return` $l$
Comments
Post a Comment