O(n) java DP


  • 0
    M
    public class Solution {
        private boolean start = false;
    public int wiggleMaxLength(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            int n = nums.length;
            int[] a = new int[n];
            int[] dp = new int[n];
            for (int i =0;i<n - 1;i++) {
                a[i + 1] = nums[i + 1] - nums[i];
            }
            dp[0] = 0;
            for (int i=1;i<n;i++) {
                if(a[i] == 0){
                    dp[i] = dp[i-1];
                    a[i] = a[i - 1];
                }
                else
                    if (start)
                        dp[i] = dp[i - 1] + (a[i] * a[i - 1]<0 ? 1 : 0);
                    else {
                        dp[i] = 1;
                        start = true;
                    }
            }
            return dp[n-1] + 1;
        }
    }
    

Log in to reply
 

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