求帮忙啊，如何写如下算法

请给出函数，实现如下功能

class Solution { public int maxRS(int[] A); }

给定一个0为起始下标的数组 A ，其中包含 N 个整数， 返回 A 中最长的连续递增子序列的起始下标， 如果不存在这样的子序列，则返回−1

例如，给定 N=10 并且

 

A[0] =  2  A[1] = 2  A[2] = 2
A[3] =  2  A[4] = 1  A[5] = 2
A[6] = -1  A[7] = 2  A[8] = 1
A[9] =  3  

 

此函数可以返回 4，因为 A 中最长的连续递增子序列的长度为 2， 同时从下标 4 开始的长度为 2 的子序列是一个连续递增子序列， 6 或者 8 同样也是正确的答案。

又例如：给定 N=3 的数组 A[0]=30, A[1]=20, A[2]=10, 此函数可以返回 0, 1, 2, 因为数组 A 的最长的连续递增子序列的长度为 1.

数组 A 中可能包含数百兆字节的数据。

假定:

• N 是 [1..1,000,000] 内的 整数;
• 数组 A 每个元素是取值范围 [−2,147,483,648..2,147,483,647] 内的 整数 .

复杂度:

• 最坏-情况下，期望的时间复杂度是 O(N);
• 最坏-情况下，期望的空间复杂度是 O(N), 输入存储除外 (不计输入参数所需的存储空间).

输入数组中的元素可以修改.

评论

13 楼 lzxz1234 2013-03-08  

    public static int maxRS(int[] array) {
        
        if(array == null || array.length == 0) return -1;
        if(array.length == 1) return 0;
        
        int maxStart = 0;
        int maxLength = 1;
        
        int currentStart = 0;
        int currentLength = 1;
        for(int i = 1; i < array.length; i ++) {
            if(array[i] > array[i - 1]) {
                currentLength ++;
            } else {
                if(currentLength > maxLength) {
//                    System.out.println("最大长度更新到：" + currentLength);
                    maxLength = currentLength;
                    maxStart = currentStart;
                }
                currentLength = 1;
                currentStart = i;
            }
        }
        return maxStart;
    }

看看如何

12 楼 java_project 2013-03-08  

如果说刚才没考虑时间复杂度,那这样...

public class MasRS {

	private static int[] A = {2,2,2,2,1,2,3,-1,2,3,4,5};
	
	public static void main(String[] args) {
		int a = maxRS(A);
		System.out.println("begin index:"+a);
	}
	
	public static int maxRS(int[] A){
		int returnvalue = -1;//begin index
		int count = 0;//step length
		int i = 0;
		while(i<A.length){
			int j=i;
			int length = 0;
			while(compArray(A,j)){
				j++;
				length++;
			}
			if(length>count){
				count = length;
				returnvalue = i;
			}
			i = j+1;
		}
		return returnvalue;
	}
	
	public static boolean compArray(int []A,int index){
		if(index>=A.length-1){
			return false;
		}
		if(A[index]<A[index+1]){
			return true;
		}else{
			return false;
		}
	}
}

11 楼 duoduodeai 2013-03-08  

享受生活 写道

java_project 写道

public class MasRS {

	private static int[] A = {2,2,2,2,1,2,-1,2,1,3};
	
	public static void main(String[] args) {
		int a = maxRS(A);
		System.out.println("begin index:"+a);
	}
	
	public static int maxRS(int[] A){
		int returnvalue = -1;//begin index
		int count = 0;//step length
		for(int i=0;i<A.length;i++){
			int j=i;
			int length = 0;
			while(compArray(A,j)){
				j++;
				length++;
			}
			if(length>count){
				count = length;
				returnvalue = i;
			}
		}
		return returnvalue;
	}
	
	public static boolean compArray(int []A,int index){
		if(index>=A.length-1){
			return false;
		}
		if(A[index]<A[index+1]){
			return true;
		}else{
			return false;
		}
	}
}

代码格式有问题？

结果貌似正确，但时间复杂度大于O(N)

小弟万分感谢！

10 楼 享受生活 2013-03-08  

java_project 写道

public class MasRS {

	private static int[] A = {2,2,2,2,1,2,-1,2,1,3};
	
	public static void main(String[] args) {
		int a = maxRS(A);
		System.out.println("begin index:"+a);
	}
	
	public static int maxRS(int[] A){
		int returnvalue = -1;//begin index
		int count = 0;//step length
		for(int i=0;i<A.length;i++){
			int j=i;
			int length = 0;
			while(compArray(A,j)){
				j++;
				length++;
			}
			if(length>count){
				count = length;
				returnvalue = i;
			}
		}
		return returnvalue;
	}
	
	public static boolean compArray(int []A,int index){
		if(index>=A.length-1){
			return false;
		}
		if(A[index]<A[index+1]){
			return true;
		}else{
			return false;
		}
	}
}

代码格式有问题？

结果貌似正确，但时间复杂度大于O(N)

9 楼 享受生活 2013-03-08  

brucewei777 写道

1.到底返回值是一个还是一个列表？
2.当递增子序列的长度为1时，还有返回的必要吗？

其实给定int[] A后，可以得到两两元素之间的差的列表
例如：
A[0] =  2  A[1] = 2  A[2] = 2
A[3] =  2  A[4] = 1  A[5] = 2
A[6] = -1  A[7] = 2  A[8] = 1
A[9] =  3 

可以得到
0，0，0，-1，1，-3，3，-1，2

然后找到你要的子序列应该就比较容易了，如果我没理解错的话

你这样做没意义。

8 楼 享受生活 2013-03-08  

哥写出来了。

7 楼 cdcx 2013-03-08  

最大的数组个数1,000,000， 每个int占用4byte，总共的内存开销是400M。所以数据全部放在内存中是没有问题。只需要一次遍历就可以找出结果。时间复杂是O(n)

6 楼 cdcx 2013-03-08  

public class RSFinder {

    static int maxRS(int data[]) {
        int maxIndex = 0;
        int maxCounter = 0;
        int rsBeginIndex = 0;
        int rsCounter = 0;
        boolean isRsBegin = false;
        for (int i = 0; i < data.length; i++) {
            if (((i + 1) < data.length) && data[i + 1] > data[i]) {
                if (!isRsBegin) {
                    rsBeginIndex = i;
                    isRsBegin = true;
                }
                rsCounter++;
            } else {
                if (rsCounter > maxCounter) {
                    maxIndex = rsBeginIndex;
                    maxCounter = rsCounter;
                }
                isRsBegin = false;
                rsCounter = 0;
            }
        }
        return maxIndex;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int data[] = { 2, 2, 2, 2, 1, 2, -1, 2, 1, 3 };
        // int data[] = {2, 3, 4, 2, 3,4,5};
        // int data[] = { 2 };
        System.out.println(" " + maxRS(data));
    }

}

5 楼 java_project 2013-03-08  

public class MasRS {

	private static int[] A = {2,2,2,2,1,2,-1,2,1,3};
	
	public static void main(String[] args) {
		int a = maxRS(A);
		System.out.println("begin index:"+a);
	}
	
	public static int maxRS(int[] A){
		int returnvalue = -1;//begin index
		int count = 0;//step length
		for(int i=0;i<A.length;i++){
			int j=i;
			int length = 0;
			while(compArray(A,j)){
				j++;
				length++;
			}
			if(length>count){
				count = length;
				returnvalue = i;
			}
		}
		return returnvalue;
	}
	
	public static boolean compArray(int []A,int index){
		if(index>=A.length-1){
			return false;
		}
		if(A[index]<A[index+1]){
			return true;
		}else{
			return false;
		}
	}
}

代码格式有问题？

4 楼 java_project 2013-03-08  

public class MasRS {

private static int[] A = {2,2,2,2,1,2,-1,2,1,3};

public static void main(String[] args) {
int a = maxRS(A);
System.out.println("begin index:"+a);
}

public static int maxRS(int[] A){
int returnvalue = -1;//begin index
int count = 0;//step length
for(int i=0;i<A.length;i++){
int j=i;
int length = 0;
while(compArray(A,j)){
j++;
length++;
}
if(length>count){
count = length;
returnvalue = i;
}
}
return returnvalue;
}

public static boolean compArray(int []A,int index){
if(index>=A.length-1){
return false;
}
if(A[index]<A[index+1]){
return true;
}else{
return false;
}
}
}

我写个简单的例子，这个不考虑数组的大小问题。如果数组很大的情况，我理解可以分段处理，比如分10或者100段，然后在每组去找开始值，然后只需要记录上个数组值的开始点，以及是否是最近的一次比对，比如说{2,1,3}这样记录开始坐标1,步长1,状态true(是否连续下个数组),如果{2,3,2}则记录0,步长1,状态false这样就不去关联下个分段数组就OK了吧。

3 楼 brucewei777 2013-03-08  

1.到底返回值是一个还是一个列表？
2.当递增子序列的长度为1时，还有返回的必要吗？

其实给定int[] A后，可以得到两两元素之间的差的列表
例如：
A[0] =  2  A[1] = 2  A[2] = 2
A[3] =  2  A[4] = 1  A[5] = 2
A[6] = -1  A[7] = 2  A[8] = 1
A[9] =  3 

可以得到
0，0，0，-1，1，-3，3，-1，2

然后找到你要的子序列应该就比较容易了，如果我没理解错的话

2 楼 cheneyjuu 2013-03-08  

递归          

1 楼 gao_xianglong 2013-03-08  

在下愚昧，没看懂你到底想这什么算法