<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;
    
    }
    
}
    



    



    
                                
                                
                                
    
	
    


    
	    
    




    








    

				
			
    
		    		
	
    
	
    
		
			

		
	
    

    


    







    
        
	



主站蜘蛛池模板：
51在线视频免费观看视频|
亚洲黄片手机免费观看|
免费国产成人18在线观看|
亚洲中文字幕丝袜制服一区|
全黄A免费一级毛片|
免费国产在线观看不卡|
免费高清A级毛片在线播放|
国产成人精品免费视频软件|
亚洲aⅴ天堂av天堂无码麻豆
|
国产精品亚洲精品|
亚洲电影在线免费观看|
亚洲国产成人九九综合|
99精品国产免费久久久久久下载|
亚洲伦理中文字幕|
永久免费AV无码网站在线观看
|
亚洲乱码在线播放|
国产香蕉九九久久精品免费|
亚洲熟妇无码一区二区三区|
色播在线永久免费视频|
午夜在线免费视频|
日韩亚洲人成在线综合日本|
91久久成人免费|
亚洲精品亚洲人成在线|
亚洲精品天堂成人片?V在线播放|
18禁超污无遮挡无码免费网站|
337p日本欧洲亚洲大胆艺术|
毛片基地免费观看|
一级毛片免费一级直接观看|
亚洲av无码不卡一区二区三区|
97性无码区免费|
免费人妻精品一区二区三区|
无码久久精品国产亚洲Av影片
|
免费人成大片在线观看播放电影
|
青青久久精品国产免费看|
亚洲无码在线播放|
久久经典免费视频|
国产成人高清亚洲一区久久|
久久亚洲高清观看|
日本免费v片一二三区|
最近2019中文免费字幕在线观看|
亚洲天堂男人影院|