2013
11-11

# Sticks Problem

Xuanxuan has n sticks of different length. One day, she puts all her sticks in a line, represented by S1, S2, S3, …Sn. After measuring the length of each stick Sk (1 <= k <= n), she finds that for some sticks Si and Sj (1<= i < j <= n), each stick placed between Si and Sj is longer than Si but shorter than Sj.

Now given the length of S1, S2, S3, …Sn, you are required to find the maximum value j – i.

The input contains multiple test cases. Each case contains two lines.

Line 1: a single integer n (n <= 50000), indicating the number of sticks.

Line 2: n different positive integers (not larger than 100000), indicating the length of each stick in order.

Output the maximum value j – i in a single line. If there is no such i and j, just output -1.

4
5 4 3 6
4
6 5 4 3


1
-1


//* @author:
import java.util.*;
public class Main {

static public void main( String [] str ) throws Exception{
Scanner sc = new Scanner(System.in);
int i, j, h, ans;

while(sc.hasNext())
{
int n=sc.nextInt();
int s[]=new int[n];
for( i=0; i< n; i++ )
s[i]=sc.nextInt();
ans = 0;
for( i=0; i< n && i+ans< n; i++ )
if( i==0 || s[i-1]>s[i] )
for( h=s[i], j=i+1; j< n; j++ )
{
if( s[i] > s[j] ) break;
if( s[j] > h )
{
h = s[j];
if( j-i > ans ) ans = j-i;
}
}

if( ans == 0 ) ans = -1;
System.out.printf( "%d\n", ans );
}

}
}

1. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”