2
回答
怎么用Java实现:单调递增子序列(动态规划)?
华为云实践训练营,热门技术免费实践!>>>   

问题描述:

给出一个由n个数组成的序列x[1..n],找出它的最长单调上升子序列。即求最大的m和a1,a2……,am,使得a1<a2<……<am且x[a1]<x[a2]<……<x[am]。

<无标签>
举报
浅诉别辞
发帖于6个月前 2回/107阅

public static int[] getSubArr(int[] pArr){
  if(pArr.length <= 1){
   return null;
  }
  int lastPoint = 0;
  int lastLength = 0;
  int currLength = 0;
  for(int i = 1; i < pArr.length; i++){
   if(pArr[i] < pArr[i-1] || i == pArr.length-1){
    currLength = i - lastPoint;
    if(currLength > lastLength){
     lastLength = currLength;
     lastPoint = i;
    }
   }
  }

  int[] result = new int[lastLength];
  Arrays.copyOfRange(result, lastPoint- lastLength, lastPoint);
  return result;
 }

把数组想象成一条波浪线,下标为横轴,值为纵轴。先找出第一个波谷值,接着找下一个波峰值,记下两个值的下标及其差值;接着找下一对,以此类推……取差值最大者。如果第一个值比第二个值大,就把第一个值看成波峰值,反之就看成波谷值,最后一个值也是一样的道理。

顶部