排序子序列

牛牛定義排序子序列為一個數組中一段連續的子序列,并且這段子序列是非遞增或者非遞減排序的。牛牛有一個長度為n的整數數組A,他現在有一個任務是把數組A分為若幹段排序子序列,牛牛想知道他最少可以把這個數組分為幾段排序子序列.

如樣例所示,牛牛可以把數組A劃分為[1,2,3]和[2,2,1]兩個排序子序列,至少需要劃分為2個排序子序列,是以輸出2

輸入描述:

輸入的第一行為一個正整數n(1 ≤ n ≤ 10^5)

第二行包括n個整數A_i(1 ≤ A_i ≤ 10^9),表示數組A的每個數字。

輸出描述:

輸出一個整數表示牛牛可以将A最少劃分為多少段排序子序列

輸入例子:

6

1 2 3 2 2 1

輸出例子:

2

AC代碼：

/*
 * flag = 0 開始
 * flag = 1 嚴格遞增（即不包含相等的情況）
 * flag = 2 嚴格遞減（即不包含相等的情況）
 * 相等的時候我們什麼也不做，最後對于我們結果加1即可
 */

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int flag = 0;
        int res = 0;
        int last = in.nextInt();
        for(int i = 1 ; i < N ; i++){
            int now = in.nextInt();
            if (flag == 0){
                if ( now > last){
                    flag = 1;
                }else if(now < last){
                    flag = 2;
                }
            }else if( flag == 1){
                if ( now < last){
                    flag = 0;
                    res++;
                }
            }else{
                if ( now > last){
                    flag = 0;
                    res++;
                }
            }
            last = now;
        }
        //res++;
        System.out.println(res);

        in.close();
    }

}           

複制