Longest swing sequence [greedy practice]

Preface

greedy / Dynamic programming / Monotonic stack , They are all high-level topics that examine logical ability , These questions need to be analyzed , Need better versatility .

One 、 Longest swing sequence

Two 、 Greedy Algorithm

1、 The conditions that greed needs to meet

Optimal substructure ： The solution of the larger problem consists of the solution of the smaller subproblem , The solution of the larger problem is determined only by the solution of one of the smaller subproblems ;
No aftereffect ： The solution in the later stage will not modify the results calculated in the previous stage ;
Greedy choice nature ： The global optimal solution can be obtained from the local optimal solution .

notes ： Among them, it is particularly important to grasp the non aftereffect . Greedy algorithm is to make the best choice in the current state and think that it can solve the problem .

2、 Thought analysis

This question , Just find the peaks and valleys in sequence , Take the peak and trough as the nodes of swing , The greedy value problem of its system .

3、code

package everyday.greed;

public class WiggleMaxLength {
    
    /* target： Find the longest wiggler sequence .  Take feifeng / Delete the valley element , But here we only need to count the length of the longest swing sequence , Not the element of the longest swing sequence , So only calculate the peak / Valley node points , It is equivalent to deleting other non peaks in disguise / Valley node . */
    public int wiggleMaxLength(int[] nums) {
    
        if (nums.length < 2) return nums.length;
        //  The core ： As long as the peak / The lowest element , That is, the maximum and minimum value , Swing up .
        int curDiff = 0, preDiff = 0, ans = 1;
        for (int i = 0; i < nums.length - 1; i++) {
    
            curDiff = nums[i + 1] - nums[i];
            //  Calculate peak  ||  Calculate Valley 
            if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
    
                ++ans;
                preDiff = curDiff;
            }
        }
        return ans;
    }
}

summary

1） Greedy practice .

reference

[1] LeetCode Longest swing sequence