Cho một mảng các số nguyên nums. Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất (LIS).
Một dãy con là dãy thu được bằng cách xóa bớt một số phần tử (hoặc không xóa phần tử nào) mà không làm thay đổi thứ tự tương đối của các phần tử còn lại.
Ví dụ 1:
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Giải thích: Dãy con tăng dài nhất là [2, 3, 7, 101] hoặc [2, 5, 7, 101], có độ dài 4.Ví dụ 2:
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4Định Dạng Đầu Vào (Input)
Một dòng chứa mảng các số nguyên nums
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là độ dài LIS
Ràng Buộc (Constraints)
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[10, 9, 2, 5, 3, 7, 101, 18]
Output:
4
Giải thích: [2, 3, 7, 101] độ dài 4
Ví dụ 2:
Input:
[0, 1, 0, 3, 2, 3]
Output:
4
Giải thích: [0, 1, 2, 3] độ dài 4
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Quy Hoạch Động O(n^2) hoặc Nhị Phân O(n log n)
Gọi dp[i] là độ dài LIS kết thúc tại chỉ số i.
dp[i] = 1 + max(dp[j]) với mọi j < i và nums[j] < nums[i].
Dữ liệu đầu vào (Input):
[10, 9, 2, 5, 3, 7, 101, 18]
Kết quả kỳ vọng (Expected Output):
4
Dữ liệu đầu vào (Input):
[0, 1, 0, 3, 2, 3]
Kết quả kỳ vọng (Expected Output):
4
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
