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

LongestIncrementSubarray

Posted on 2009-10-26 11:39 小强摩羯座 阅读(173) 评论(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;
    }
}



只有注册用户登录后才能发表评论。
网站导航: