CodeCollection2018
8/23/2019 - 6:10 AM

Wiggle Subsequence

例如[3,5,1,10,9,12]这种相邻两个数之间的差距呈现正负数交替的情况的数组叫做“wiggle array”。给定一个数组，求其中最长的wiggle子序列，子序列不一定每个元素相邻。 思路：这些问题有通用的解法，对于子序列问题可以令数组dp[i]表示以第i个数字结尾的自序列的最长（小）长度，那么有dp[i] = dp[k]+1, k=0,1,2…,i-1, 只要数组第k个数字满足条件。最后的答案取dp中的最大（小）值。但是这道题需要加另一个数组才可以，记录nums[i]所处的最长的wiggle 子序列中相较于前一个数是上升还是下降，因为后面要用到这个来构成wiggle 子序列。而且这种题的最终答案不是最后一个数字，而是需要在循环中记录比较。

wiggle subseq
content_copyfile_download
public int longestWiggleSubseq(int [] nums){
  if(nums==null || nums.length ==0 ) return 0;
  int [] dp = new int[nums.length]{1};
  int [] sign = new int[nums.length];//+1 up,-1 down
  int res = Integer.MIN_VALUE;
  for(int i = 1; i < nums.length; i++){
    int pre_pos = i;
    for(int j = i-1; j >= 0 ; j--){
      if((j==0 || sign[j]*(nums[i]-nums[j])<0) && dp[i]<dp[j]+1){
        pre_pos = j;
        dp[i]=dp[j]+1;
      }
    }
    sign[i]=nums[i]>nums[pre_pos]?1:-1;
    res = Math.max(res,dp[i]);
  }
  return res;
}