白駿-2491号(数列)


質問元:https://www.acmicpc.net/problem/2491
質問する

  • 0から9の数字からなるNの数字がリストされた数列があります.この数列では、連続的に大きくなる(同じものを含む)または連続的に小さくなる(同じものを含む)数列の中で最も長い数列を見つけ、プログラムを記述してその長さを出力する.

  • 例えば、数列1、2、2、4、4、5、7、2の場合、1≦2≦2≦4≦4≦5≦7≦7≦7が最長区間となるため、出力長は8となる.4、1、3、3、2、2、9、2、3を数えると、3≧3≧2≧2が最長区間であり、その長さは4である.また、1、5、3、6、4、7、1、3、2、9、5の場合、連続的に大きくなったり小さくなったりする数列長が3より大きくなったりすることはないので、2を出力する必要がある.
  • import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;
    
    public class Main {
    
        public static void main(String[] args) throws IOException {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(reader.readLine());
            int[] arr = new int[N];
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    
            int result = 1;
            int ascCount = 1;
            int descCount = 1;
    
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(tokenizer.nextToken());
            }
    
            int temp = arr[0];
    
            for (int i = 1; i < N; i++) {
                if (arr[i] > temp) {
                    ascCount++;
                    result = Math.max(descCount, result);
                    descCount = 1;
                } else if (arr[i] < temp) {
                    descCount++;
                    result = Math.max(ascCount, result);
                    ascCount = 1;
                } else {
                    ascCount++;
                    descCount++;
                }
    
                temp = arr[i];
            }
    
            result = Math.max(Math.max(ascCount, descCount), result);
            System.out.println(result);
        }
    
    }
    
  • の解決策を考え出すのに長い時間がかかった.
  • 主な論理は2回の探索を行うだけである.一度は大きいが,一度は小さい
  • に達するために,最初は大きくなる探索と小さくなる探索に分けて繰り返し処理を行ったが,コードが完成した後,1回繰り返し可能であるため,合わせて解答を行った.