获得最长单调递增子串的一种解法，很经典！！ - 黑马程序员技术交流社区

获得一个整形数组中的最长单调递增子串，并将其打印出来。
假设源数据数组为arr，长度为n，用数组mem[n]来记录以0=<i<n下表为结尾元素的递增子串的个数,path[][]来记录以0=<i<n为下表元素的递增子串的各数据值。
根据算法 mem0]=1, mem[i] = max{mem[k]}+1 (其中 0=<k<i,arr[k]<arr[i] )
public class GetMaxSubInt
{
public static void main(String[] args)
{
int[] a = {1,4,3,6,5,9};
MaxSubOrder(a);
}
public static void MaxSubOrder(int[] arr)
{
int n = arr.length; //数据个数
int[] mem = new int[n]; //急速每个递增子串的数据个数
int[][] path = new int[n][n+1]; //记录最长子串的值，其中path[i][n]用来记录以i未下表元素结尾的递增子串的数据个数
int i=0,j=0,k=0;
int count = 0; //计数器
for(i=0,mem[0]=1; i<n; i++)
{
path[i] = new int[n+1];
count = 0;
for(j=0,k=0; j<i; j++)
{
if((arr[j]<=arr[i]) && (k<mem[j])) // 满足 0=<j<i arr[j]<arr[i] && 获得mem[i]
{
k = mem[j];
path[i][count++] = arr[j];
}
}
mem[i] = k+1;
path[i][count++] = arr[i];
path[i][n] = count;
}
//获取mem[]中的最大值，即为最长递增子串值
for(i=0,k=0; i<mem.length; i++)
{
if(mem[i] > k)
{
k = mem[i];
j = i;
}
}
//输出最长递增子串
for(i=0; i<path[j][n]; i++)
{
System.out.print(path[j][i]+" ");
}
}
}
算法所用时间为O(n*n)。

复制代码