一个JAVA语言的考试题目

来源：百度知道 编辑：UC知道 时间：2024/06/05 21:11:50
题目：1 假设使用者随意输入 N 个整数，请从中找出一个长度最长的递增子串列。例如：当使用者依序输入 15,7,6,9,11,12,4 时，输出为 6,9,11,12。

2 在所有的递增子串列中选取其中和最大的子串列。
例如：当使用者依序输入 9,15,7,6,11,12,4 时，输出为 9,11,12。

public class LongestUpsequence
{

public int maxLength(int [] a)
{

int n = a.length;

int[] B = new int[n+1];

B[0]=-10000;

B[1]=a[0];

int Len = 1;

int p,r,m;

for(int i = 1;i<n;i++)

{

p=0;r=Len;

while(p<=r)

{

m = (p+r)/2;

if(B[m]<=a[i]) p = m+1;

else r = m-1;

}

B[p] = a[i];

if(p>Len) Len++;

}

return Len;

}

动态规划

这是属于算法的问题，是个经典的最长子序列问题，应该动态规划和贪心算法都可以作～

好深啊。不懂。。可以具体说说么？？

我要下班了
我回去做出来给我加分