與心靈對話

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

LongestIncrementSubarray

Posted on 2009-10-26 11:39 小強摩羯座閱讀(181) 評論(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;

}

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: AC算法使用例子使用用最小堆來找最大的K個數 zz求二叉樹中節點的最大距離 zz精華游戲算法整理 pku3233　矩陣相乘的反復平方法和矩陣等比和計算構造方法最小表示法排序算法、時間復雜度與信息熵 zz 傳說中效率最高的最大流算法(Dinic) zz 最短路徑之 SPFA算法 zz C語言編一個簡單的計算器

與心靈對話

導航

常用鏈接

留言簿(14)

隨筆分類

隨筆檔案

文章檔案

相冊

收藏夾

技術基礎

技術相關

研究方向

算法類

搜索

最新評論

閱讀排行榜

評論排行榜

LongestIncrementSubarray