Simple DP(?) Solution


  • 0
    L

    The max length of wiggle subsequence up to i is either the max length at i - 1 plus 1, or just the answer at (i - 1). So we can construct two arrays, which I combine into a 2D array in my solution, to track the results we need. In my codes, T[0] records the max length so far while T[1] tracks increase, decrease and equal: T[1][i] > 0 if nums[i] > nums[i - 1], T[1][i] = T[1][i - 1] if nums[i] = nums[i - 1].

    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums.length < 2) {
                return nums.length;
            } else {
                int[][] T = new int[2][nums.length];
                T[0][0] = 1;
                T[1][0] = 0;
                for (int i = 1; i < nums.length; i++) {
                    if ((nums[i] - nums[i - 1]) * T[1][i - 1] < 0) { # if the numbers are alternating
                        T[0][i] = T[0][i - 1] + 1;
                        if (T[1][i - 1] < 0) {
                            T[1][i] = 1;
                        } else {
                            T[1][i] = -1;
                        }
                    } else if (T[1][i - 1] == 0) { # this is true only if nums[0] = nums[1] = nums[2] =...= nums[i - 1]
                        if (nums[i] - nums[i - 1] > 0) {
                            T[0][i] = 2;
                            T[1][i] = 1;
                        } else if (nums[i] - nums[i - 1] == 0) {
                            T[0][i] = 1;
                            T[1][i] = 0;
                        } else {
                            T[0][i] = 2;
                            T[1][i] = -1;
                        }
                    } else { # not alternating
                        T[0][i] = T[0][i - 1];
                        T[1][i] = T[1][i - 1];
                    }
                }
                return T[0][nums.length - 1];
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.