<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        


    
	
    
		
			


    

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


    		
	
    
	
    
		
			
		
		
			
    
				
					
	
    
		
    
			
    
				LongestIncrementSubarray
			
    
 			Posted on 2009-10-26 11:39 小強摩羯座 閱讀(179) 評論(0)  編輯  收藏  所屬分類: 算法編程 
			
			


		
    
		
    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]了已經
    
                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]了已經
    
            //    if (a[i] > maxV[j] && 
    
                if(a[i] < maxV[j + 1])//a[i],對應到maxV[j+1]位置上，并選小的
    
                    maxV[j + 1] = a[i];
    
        }
    
            return maxLIS;
    
    }
    
}
    



    



    
                                
                                
                                
    
	
    


    
	    
    




    








    

				
			
    
		    		
	
    
	
    
		
			

		
	
    

    


    







    
        
	



主站蜘蛛池模板：
中文日韩亚洲欧美制服|
国产精品亚洲一区二区三区在线|
久久久久亚洲精品天堂|
女同免费毛片在线播放|
亚洲Av无码专区国产乱码DVD|
成av免费大片黄在线观看|
亚洲午夜av影院|
久久免费线看线看|
91精品国产亚洲爽啪在线影院|
4399影视免费观看高清直播|
亚洲国产夜色在线观看|
99re热免费精品视频观看|
亚洲成av人无码亚洲成av人|
国产三级电影免费观看|
国产99久久久国产精免费|
区久久AAA片69亚洲|
久久中文字幕免费视频|
亚洲成人福利在线观看|
午夜视频免费观看|
免费无遮挡无码视频在线观看|
91麻豆精品国产自产在线观看亚洲|
成人爽a毛片免费|
亚洲免费在线视频观看|
国产在线观看免费视频播放器|
国产福利免费视频|
亚洲精品国产成人|
美女黄网站人色视频免费国产|
午夜在线免费视频|
久久亚洲精品成人无码网站|
啦啦啦手机完整免费高清观看|
日韩a毛片免费观看|
日韩亚洲Av人人夜夜澡人人爽
|
水蜜桃视频在线观看免费播放高清
|
国产男女猛烈无遮挡免费视频
|
外国成人网在线观看免费视频|
亚洲国产高清美女在线观看|
国产在线ts人妖免费视频|
国产免费拔擦拔擦8X高清在线人|
色天使亚洲综合在线观看|
国产亚洲AV夜间福利香蕉149|
2021国内精品久久久久精免费|