2 solutions & Proof of O(N) greedy algorithm


  • 0
    L

    First solution: dynamic programming
    we keep 2 arrays:
    inc[i] - longest wiggle sequence ending increasing at position i
    dec[i] - longest wiggle sequence ending decreasing at position i
    There is a good tutorial for this problem, you can check it here:
    http://www.hiredintech.com/algorithm-design/idea-generation/
    Time: O(N^2), Space: O(N)

    Code:

    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] inc = new int[n];
        int[] dec = new int[n];
        int best = 1;
    
        Arrays.fill(inc, 1);
        Arrays.fill(dec, 1);
    
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] < nums[j]) {
                    // decreasing from j
                    dec[i] = Math.max(dec[i], inc[j] + 1);
                } else if (nums[i] > nums[j]) {
                    // increasing from j
                    inc[i] = Math.max(inc[i], dec[j] + 1);
                }
            }
            best = Math.max(dec[i], inc[i]);
        }
        return best;
    }
    

    Second solution: greedy
    One key observation of the problem is:
    No matter where your longest wiggle sequence ends, it can always start from position 0. Why? Here is a proof by contradiction:
    Suppose you can not find the longest wiggle sequence starting at position 0, then it must start at some position i, where i > 0. There are three cases:
    Case 1: nums[i] > nums[0]
    Case 2: nums[i] < nums[0]
    Case 3: nums[i] = nums[0]
    In all above three cases, you can safely extend the start of your longest wiggle sequence to position 0. You will at least achieve the same length if not better.

    Therefore, we can start from position 0 and keep tracking of 3 things:
    boolean isIncreasing - is current subsequence increasing or decreasing
    curMin - if decreasing, the minimum value of the current decreasing sequence
    curMax - if increasing, the maximum value of the current increasing sequence

    In my code below, I tried to find the first increasing or decreasing instance to initialize isIncreasing, curMin and curMax, and then perform the greedy approach. Code is kind of lengthy, can be further improved somehow i think.

    One last question to think about: are the above 2 approach still working if we define the wiggle sequence as "strictly alternate or equal"?

    public static int wiggleMaxLength2(int[] nums) {
        // try an greedy approach O(N) time complexity
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int best = 1;
        int curMin = nums[0];
        int curMax = nums[0];
    
        // find the first increasing or decreasing
        boolean isIncreasing = false;
        int startIdx = 0;
        while (startIdx < n) {
            if (nums[startIdx] > nums[0]) {
                // find increasing
                isIncreasing = true;
                best = 2;
                curMax = nums[startIdx];
                break;
            } else if (nums[startIdx] < nums[0]) {
                // find decreasing
                isIncreasing = false;
                best = 2;
                curMin = nums[startIdx];
                break;
            } else {
                startIdx += 1;
            }
        }
    
        for (int i = startIdx + 1; i < n; i++) {
            if (isIncreasing) {
                if (nums[i] > curMax) {
                    curMax = nums[i];
                } else if (nums[i] < curMax) {
                    best += 1;
                    isIncreasing = false;
                    curMin = nums[i];
                }
            } else {
                if (nums[i] < curMin) {
                    curMin = nums[i];
                } else if (nums[i] > curMin) {
                    best += 1;
                    isIncreasing = true;
                    curMax = nums[i];
                }
            }
        }
        return best;
    }
    
    

Log in to reply
 

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