轩辕互动面试题目-----最大递增子序列（转）

数组A中存放很多数据，比如A={1,2,3,4,3,2,1,4,8,9,10};其中1,2,3,4/1,4,8,9,10都是递增子序列，1,4,8,9,10是最长的递增子序列。

寻找数组中的最长子序列，返回起始的索引值，如果没有递增子序列，那么返回-1.

实际就是连续判断A[i]是否比A[i-1]大，下面是我的代码：

int maxasds(int A[], int n)   
{   
    int     lastCount;   
    int     count;   
    int     max, idx;   
    int     i;   
  
    max = 1;   
    idx = -1;   
    lastCount = 0;   
    count = 1;   
    for(i = 1; i < n; i++) {   
        if(A[i] > A[i - 1]) {   
            lastCount = 0;   
            count++;   
        } else {   
            lastCount = count;   
            count = 1;   
        }   
  
        if(max < lastCount) {   
            max = lastCount;   
            idx = i - lastCount;   
        }   
    }   
  
    return idx;   
}  

评论

2 楼 爱园园真是太好了 2017-01-03  

package zj.hy.love;


/**
 * 数组A中存放很多数据，比如A={1,2,3,4,3,2,1,4,8,9,10};<br>
 * 其中1,2,3,4/1,4,8,9,10都是递增子序列，<br>
 * 1,4,8,9,10是最长的递增子序列。<br>
 * 寻找数组中的最长子序列，返回起始的索引值，<br>
 * 如果没有递增子序列，那么返回-1. 
 * @author ZJ
 * @since 2017-1-3
 */
public class Ques20170103_01 {
	
	/**
	 * 寻找最长序列的其实索引
	 * @return
	 */
	public int findIndex(int[] a){
		
		int len = a.length;
		int count = 0;
		int lastCount = 0;
		int index = 0;
		for (int i = 0; i < len-1; i++) {	
			if(count>lastCount){
				lastCount = count;
				index = i - lastCount;
			}
			if(a[i+1]>a[i]){
				count++;
			}else{	
				count = 0;				
			}				
		}
		if(lastCount==0){
			index = -1;
		}
		return index;
	}
	
	public static void main(String[] args) {
		
		Ques20170103_01 ques = new Ques20170103_01();
		int[] a = {1,2,3,1,2,3,4,1,2,3,4,5};
		System.out.println(ques.findIndex(a));
	}
}

1 楼 星情泪 2010-01-07  

有点不太明白你方法的第二个参数的含义，用a.length()不可以代替吗？

还有如果我把{1,2,3,4,3,2,1,4,8,9,10}传递过去，应该返回6吧，但你的方法返回了0（当最长子串位于大数组的末端时）