Dãy con tăng dài nhất (bản dễ)

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

corona

Dạng bài

Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một dãy số nguyên gồm N phần tử \(A[1], A[2], ... A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],... A[i_k]\) thỏa mãn
\(i_1 < i_2 < ... < i_k\) và \(A[i_1] < A[i_2] < .. < A[i_k]\).

Yêu cầu:

Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 ≤ N ≤ 1000\))
Dòng thứ 2 ghi N số nguyên \(A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 1000000)\).

Kết quả

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Test 1

Input

6
1 2 5 4 6 2

Output

Nguồn: vn.spoj

Bình luận

def longest_increasing_subsequence_length(arr):
    n = len(arr)
    lis = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    return max(lis)
##################################################################
N = int(input())
A = list(map(int, input().split()))
print(longest_increasing_subsequence_length(A))

python 3 nha

6 bình luận nữa