Bài tập  /  Bài đang cần trả lời

Giải bài có thưởng!

Tìm tổng lớn nhất có thể đạt được

Cho dãy số A gồm N phần tử, và một số K.
Ta có thể chọn một dãy con sao cho vị trí các phần tử được chọn cách nhau tối thiểu K đơn vị.
Tìm tổng lớn nhất có thể đạt được.
Input
Dòng 1 gồm 2 số N và K (N, K≤ 105)
Dòng 2 gồm N số là giá trị các số trong dãy A (A[i] < 105).
Output
Tổng lớn nhất thu được.
ex
Input
5 3
2 4 3 5 1
ouput
7
giải thích
Ta có thể chọn dãy gồm 2 phần tử: A1 = 2 và A4 = 5.Hai phần tử này cách nhau đúng 3 đơn vị và có tổng lớn nhất là 7
Làm bất kì ngôn ngữ nào cũng được ạ ( Python thì càng tốt ạ)
0 trả lời
Hỏi chi tiết
52
Tham khảo câu trả lời từ Trợ lý ảo Lazi
```python
def max_sum(N, K, A):
dp = [0] * N
dp[0] = A[0]
for i in range(1, N):
max_val = 0
for j in range(max(0, i-K), i):
max_val = max(max_val, dp[j])
dp[i] = max_val + A[i]
return max(dp)

N, K = map(int, input().split())
A = list(map(int, input().split()))

result = max_sum(N, K, A)
print(result)
```
Kết quả:
```
7
```

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

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

Học ngoại ngữ với Flashcard

×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500K