递增子序列

[编程题]递增子序列

热度指数：510 时间限制：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)

封装成帧

leetcode334

// 动态规划
public boolean increasingTriplet(int[] nums) {
    if (nums == null || nums.length < 3)
        return false;
    int[] dp = new int[nums.length];
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            if (dp[i] > 1)
                return true;
        }
    }
    return false;
}
// 着眼于中间的那个值
public boolean increasingTriplet_2(int[] nums) {
    if (nums == null || nums.length < 3) {
        return false;
    }
    int min = Integer.MAX_VALUE;
    int mid = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] <= min) {
            min = nums[i];
        } else if (nums[i] <= mid) {
            mid = nums[i];
        } else {
            return true;
        }
    }
    return false;
}

发表于 2019-12-06 22:25:26 回复(0)

{球球offer}

//遍历数据，确定从起始点到该点的最小数据值、和左边拥有更小数据的第二小数据中的最小值
//min记录最小数据，second记录长度为2的递增的最小的第二个值，如果当前遍历的数据大于second则存在长度为三的递增

#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	int tmp, min = 0, second = 0;
	cin >> min;
	while (cin >> tmp) {
		if (tmp > min) {
			second = tmp;
			break;
		}
		else if (tmp < min) {
			min = tmp;
		}
	}
	while (cin >> tmp) {
		if (tmp < min) {
			min = tmp;
		}
		else if (tmp > min) {
			if (tmp > second) {
				cout << "true";
				system("pause");
				return 0;
			}
			if (tmp < second)
				second = tmp;
		}
	}
	cout << "false";
	system("pause");
	return 0;
}

发表于 2019-09-09 18:37:17 回复(0)