e****e
发帖数: 418 | 1 Given a vector of integers, find the longest consecutive sub-sequence of
increasing numbers. If two sub-sequences have the same length, use the one
that occurs first. An increasing sub-sequence must have a length of 2 or
greater to qualify.
Example input:
[1 0 1 2 3 0 4 5]
Result:
[0 1 2 3] | e****e
发帖数: 418 | 2 我的解法，总觉得用Java写还有更好的。
public class LongestConsecutiveSubsequence {
private int longestLCSStartPos = 0;
private int longestLCSCount = 0;
public Vector lcs(Vector input) {
if( input == null || input.size() < 2 )
throw new RuntimeException( "Invalid input." );
lcs( input, 0 );
if ( longestLCSCount < 2 )
throw new RuntimeException( "lcs length is less than 2." );
Vector r = new Vector();
for( int i = 0 ; i < longestLCSCount; i++ )
r.add( input.get( i + longestLCSStartPos ) );
return r;
}
private void lcs(Vector input, int startPos ) {
if( startPos == input.size() - 1 )
return;
int lcsStartPos = findNextBottomPos( input, startPos );
int lcsEndPos = findNextTopPos( input, lcsStartPos );
int lcsCount = lcsEndPos - lcsStartPos + 1;
if( lcsCount > longestLCSCount) {
longestLCSStartPos = lcsStartPos;
longestLCSCount = lcsCount;
}
lcs( input, lcsEndPos );
}
private int findNextBottomPos( Vector input, int startPos ) {
while( startPos + 1 < input.size() && input.get( startPos + 1 ) <=
input.get( startPos ) )
startPos++;
return startPos;
}
private int findNextTopPos( Vector input, int startPos ) {
while( startPos + 1 < input.size() && input.get( startPos + 1 ) >
input.get( startPos ) )
startPos++;
return startPos;
}
} | r**h
发帖数: 1288 | 3 连续递增子串的话，从左往右扫一轮不就可以了吗
int i=0, j, maxLength=0;
while(i < A.length-1){
while(A[i]> A[i+1] && i
i++;
j = i+1;
while(jA[j-1])
j++;
if(maxLength < j-i)
maxLength = j-i;
i = j;
}
if(maxLength <= 1)
return 0;
return maxLength;
【在 e****e 的大作中提到】
: Given a vector of integers, find the longest consecutive sub-sequence of
: increasing numbers. If two sub-sequences have the same length, use the one
: that occurs first. An increasing sub-sequence must have a length of 2 or
: greater to qualify.
: Example input:
: [1 0 1 2 3 0 4 5]
: Result:
: [0 1 2 3]
|
|
