online advertising

Saturday, July 23, 2016

LeetCode OJ - Wiggle Subsequence

Problem:

Please find the problem here.

Analysis:

The key idea is that we should pick the endpoints and the local extrema. Intuitively, that make sense, but how do we formally prove that this is going to be an optimal solution?

As a first step, conceptually, we eliminate the runs of duplicated values and leave only one. They does not impact the solution in anyway, since we require strictly alternating, and you can take at most one from that run anyway.

Next, now we can break the sequence into runs of either strictly increasing or strictly decreasing sequences, and they are alternating. Apparently, we can have at most two points in a strict sequence.

We claim that any feasible sequence can be transformed into a sequence that take the local optima and endpoints only. For any strict sequence, if it has a first point, we move it to the left endpoint if it is available, otherwise we move it to the right, and if it has a second point, we move it to the right endpoint. The transformation is feasible if we never take the same endpoint twice. Here we claim, for any feasible sequence it cannot.

Without loss of generality, let say we have one increasing subsequence with two points (a, b) and then a decreasing subsequence with also two points (c, d), that will force us to duplicate an endpoint, but note that if that's the case, then we have a > b < c < d, a two consecutive drops, which is no longer a valid wiggle sequence.

Solution:

With the proof we have, it is not hard to write the code to find the extremas. The only complication is the possibility that we have continuous duplicated entries at the end, and we must NOT take the last point in that case.

Special thanks to Cody Ohlsen who inspired the solution.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/wiggle-subsequence/

#include "LEET_WIGGLE_SUBSEQUENCE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_WIGGLE_SUBSEQUENCE
{
    class Solution
    {
    public:
        int wiggleMaxLength(vector<int>& nums)
        {
            if (nums.size() == 0)
            {
                return 0;
            }
            if (nums.size() == 1)
            {
                return 1;
            }
            bool initial = true;
            bool is_max = true;
            int last = 0;
            int counter = 1;
            for (int i = 1; i < nums.size(); i++)
            {
                if (initial)
                {
                    if (nums[i] != nums[i - 1])
                    {
                        is_max = nums[i - 1] < nums[i];
                    }
                    initial = false;
                }
                else
                {
                    if (is_max)
                    {
                        if (nums[i - 1] > nums[i])
                        {
                            last = nums[i - 1];
                            counter++;
                            is_max = false;
                        }
                    }
                    else
                    {
                        if (nums[i - 1] < nums[i])
                        {
                            last = nums[i - 1];
                            counter++;
                            is_max = true;
                        }
                    }
                }
            }
            if (nums[nums.size() - 1] != last)
            {
                counter++;
            }

            return counter;
        }
    };
};

using namespace _LEET_WIGGLE_SUBSEQUENCE;

int LEET_WIGGLE_SUBSEQUENCE()
{
    Solution solution;
    int case1_array[] = { 1,7,4,9,2,5 };
    int case2_array[] = { 1,17,5,10,13,15,10,5,16,8 };
    int case3_array[] = { 1,2,3,4,5,6,7,8,9 };
    vector<int> case1_vector(case1_array, case1_array + _countof(case1_array));
    vector<int> case2_vector(case2_array, case2_array + _countof(case2_array));
    vector<int> case3_vector(case3_array, case3_array + _countof(case3_array));
    cout << solution.wiggleMaxLength(case1_vector) << endl;
    cout << solution.wiggleMaxLength(case2_vector) << endl;
    cout << solution.wiggleMaxLength(case3_vector) << endl;
    return 0;
}

No comments :

Post a Comment