递增子序列

[编程题]递增子序列

热度指数：507 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

判断一个无序数组中是否存在长度为3的递增子序列。（不要求连续）（满足O(n)的时间复杂度和O(1)的空间复杂度。）

输入描述:

第一行一个正整数 1 <= n <= 100000

第二行n个整数a1,a2,...,an，(1<=ai<=1e9)

输出描述:

如果存在，输出"true",否则输出"false"。（不含引号）。

示例1

输入

5
12 8 36 9 20

输出

true

算法知识视频讲解

Java

来学习的小张

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i <n;i++){
            arr[i] = sc.nextInt();
        }
        int first = arr[0];
        int second = Integer.MAX_VALUE;
        boolean flg = false;
         for(int i = 1;i < n;i++){
             if(arr[i] < first){
                 first = arr[i];
             }else if(arr[i] > first && arr[i] < second){
                 second = arr[i];
             }else if(arr[i] > first && arr[i] > second){
                 flg = true;
                 break;
             }
         }
        if(flg){
            System.out.println("true");
        }else{
            System.out.println("false");
        }
    }
}

发表于 2022-04-08 09:12:01 回复(0)