Cho một dãy <!--[if gte msEquation 12]>N<!--[endif]--> các số nguyên, tìm dãy con dài nhất từ dãy đã cho sao cho trị tuyệt đối của bất kì <!--[if gte msEquation 12]-->2<!--[endif]--> phần tử nào đều nhỏ hơn hoặc bằng <!--[if gte msEquation 12]-->1<!--[endif]--> .
Dữ liệu vào: Vào từ tệp văn bản subarr.inp có dạng:
· Dòng đầu ghi số nguyên N, trong đó: <!--[if gte msEquation 12]>2≤n≤100<!--[endif]-->
· Dòng thứ hai ghi <!--[if gte msEquation 12]>N<!--[endif]--> số nguyên <!--[if gte msEquation 12]-->ai<!--[endif]--> trong đó <!--[if gte msEquation 12]-->0<ai<100<!--[endif]-->
Kết quả: In ra tệp văn bản subarr.out một số nguyên: số phần tử của dãy con dài nhất tìm được.
Ví dụ:
subarr.inp
subarr.out
Giải thích
9
1 1 2 2 4 4 5 5 5
5
Dãy thỏa mãn là {1,1,2,2} và {4,4,5,5,5} vì giữa hai phần tử bất kì hơn kém nhau không quá 1 đơn vị. Dãy 2 dài hơn, có 5 phần tử.
6
4 6 5 3 3 1
3
Chỉ có 1 dãy thỏa mãn và dài nhất là {4,3,3}
6
1 2 2 3 1 2
5
Dãy thỏa mãn là {1,2,2,1,2} có 5 phần tử.
Bằng cách nhấp vào Đăng nhập, bạn đồng ý Chính sách bảo mật và Điều khoản sử dụng của chúng tôi. Nếu đây không phải máy tính của bạn, để đảm bảo an toàn, hãy sử dụng Cửa sổ riêng tư (Tab ẩn danh) để đăng nhập (New Private Window / New Incognito Window).
def soln(): with open('subarr.inp', 'r') as f: N = int(f.readline().strip()) a = [int(x) for x in f.readline().strip().split()]
dp = [1] * N for i in range(1, N): for j in range(i): if abs(a[i] - a[j]) <= 1: dp[i] = max(dp[i], dp[j] + 1) with open('subarr.out', 'w') as f: f.write(str(max(dp)))soln()
Tham gia Cộng đồng Lazi trên các mạng xã hội | |
Fanpage: | https://www.fb.com/lazi.vn |
Group: | https://www.fb.com/groups/lazi.vn |
Kênh FB: | https://m.me/j/AbY8WMG2VhCvgIcB |
LaziGo: | https://go.lazi.vn/join/lazigo |
Discord: | https://discord.gg/4vkBe6wJuU |
Youtube: | https://www.youtube.com/@lazi-vn |
Tiktok: | https://www.tiktok.com/@lazi.vn |
Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi
Vui | Buồn | Bình thường |