posts - 195, comments - 34, trackbacks - 0, articles - 1
          


          		
	
          
	
          
		
			
		
		
			
          
				
					
	
          
		
          
			
          
				LongestIncrementSubarray
			
          
 			Posted on 2009-10-26 11:39 小強(qiáng)摩羯座 閱讀(181) 評(píng)論(0)  編輯  收藏  所屬分類(lèi): 算法編程 
			
			


		
          
		
          package com.dwq.algo;
          

          
          import java.util.ArrayList;
          

          
          public class LongestIncrementSubarray
          
          {
          

          
              public static void main(String[] args)
          
              {
          
                  int[] a = { 3, -1, 2, 4,3, 5, -8, 6 };
          

          
                  int len = LIS2(a);
          
        System.out.println(len);
          
                  for (int i : re)
          
            System.out.print(i           + ", ");
          
    }
          

          
              static ArrayList<Integer> re = new ArrayList<Integer>();
          

          
              static int LIS(int[] a)
          
              {
          
                  int[] lis = new int[a.length];
          
                  int maxL = -1;
          
                  int max = 0;
          
                  for (int i = 0; i < a.length; i++)
          
                  {
          
            lis[i]           = 1;
          
                      for (int j = 0; j < i; j++)
          
                      {
          
                          if (a[j] < a[i] && lis[j] + 1 > lis[i])
          
                          {
          
                    lis[i]           = lis[j] + 1;
          
                              if (lis[i] > maxL)
          
                              {
          
                        maxL           = lis[i];
          
                        max           = a[i];
          
                        re.add(a[j]);
          
                    }
          
                }
          
            }
          
        }
          
        re.add(max);
          
                  return maxL;
          
    }
          

          
              static int LIS2(int[] a)
          
              {
          
                  int[] maxV = new int[a.length + 1];
          
        maxV[          0] = Integer.MIN_VALUE;
          
        maxV[          1] = a[0];
          

          
                  int lis[] = new int[a.length];
          
                  for (int i = 0; i < lis.length; i++)
          
            lis[i]           = 1;
          
                  int maxLIS = 1;
          
                  for (int i = 1; i < a.length; i++)
          
                  {
          
                      int j;
          
                      for (j = maxLIS; j > 0; j--)
          
                      {
          
                          if (a[i] > maxV[j])
          
                          {
          
                    lis[i]           = j + 1; 
          
                              break;
          
                }
          
            }
          
                      if (lis[i] > maxLIS)
          
                      {
          
                maxLIS           = lis[i];
          
                maxV[lis[i]]           = a[i];
          
            }           else //前面有a[i] > maxV[j]了已經(jīng)
          
                      if (a[i] > maxV[j] && a[i] < maxV[j + 1])//后面的有選小的
          
                          maxV[j + 1] = a[i];
          
        }
          
                  return maxLIS;
          
    }
          
              static int LIS3(int[] a)
          
              {
          
                  int[] maxV = new int[a.length + 1];
          
        maxV[          0] = Integer.MIN_VALUE;
          
        maxV[          1] = a[0];
          

          
                  int lis[] = new int[a.length];
          
                  for (int i = 0; i < lis.length; i++)
          
            lis[i]           = 1;
          
                  int maxLIS = 1;
          
                  for (int i = 1; i < a.length; i++)
          
                  {
          
                      int j;
          
                      for (j = maxLIS; j > 0; j--)
          
                      {
          
                          if (a[i] > maxV[j])
          
                          {
          
                    lis[i]           = j + 1; 
          
                              break;
          
                }
          
            }
          
                      if (lis[i] > maxLIS)
          
                      {
          
                maxLIS           = lis[i];
          
                maxV[lis[i]]           = a[i];
          
            }          // else //前面有a[i] > maxV[j]了已經(jīng)
          
                  //    if (a[i] > maxV[j] && 
          
                      if(a[i] < maxV[j + 1])//a[i],對(duì)應(yīng)到maxV[j+1]位置上，并選小的
          
                          maxV[j + 1] = a[i];
          
        }
          
                  return maxLIS;
          
    }
          
}
          



          



          
                                
                                
                                
          
	
          


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			

		
	
          

          


    







          
        
	




主站蜘蛛池模板：
寻甸|
泽州县|
手游|
奈曼旗|
革吉县|
若尔盖县|
长治县|
安图县|
双峰县|
吉安县|
寿光市|
绥化市|
新巴尔虎右旗|
晋城|
安龙县|
汉寿县|
深州市|
澄江县|
滕州市|
清苑县|
新化县|
兰州市|
明光市|
澄江县|
启东市|
济源市|
泾阳县|
灵武市|
金乡县|
曲靖市|
义乌市|
黄山市|
茶陵县|
广汉市|
佛教|
深水埗区|
朝阳市|
新晃|
汽车|
阿克苏市|
福贡县|