常考面试算法题之贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪心算法基本思路

1.建立数学模型来描述问题。　　
2.把求解的问题分成若干个子问题。　　
3.对每一子问题求解，得到子问题的局部最优解。　　
4.把子问题的解局部最优解合成原来解问题的一个解。　　
实现该算法的过程：　　
从问题的某一初始解出发；　　
while 能朝给定总目标前进一步
do　　求出可行解的一个解元素；　　
由所有解元素组合成问题的一个可行解。

排序子序列

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为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最少划分为多少段排序子序列
示例1
输入
6
1 2 3 2 2 1
输出
2

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int[] num = new int[m];
        for (int i = 0; i < m; i++) {
            num[i] = scanner.nextInt();
        }
 
        System.out.println(NewSort(m, num));
    }
 
    public static int NewSort(int m, int[] num) {
        if (m <= 0) {
            return -1;
        }
        int count = 1;
 
        int flags = 0;
        for (int i = 1; i < m; i++) {
            if (num[i] > num[i - 1]) {
                if(flags==0){
                    flags=1;
                }
                if(flags==-1){
                    flags=0;
                    count++;
                }
            } else if (num[i] < num[i - 1]) {
                if(flags==0){
                    flags=-1;
                }
 
                if(flags==1){
                    count++;
                    flags=0;
                }
 
            }
        }
        return count;
    }
}