Cho 1 dãy số nguyên có n số a1, a2 … an. Làm thế nào để in ra một đoạn con có ít nhất k phần tử từ dãy đó sao cho tổng các số nguyên thuộc đoạn là lớn nhất.
(P/s subtask 3: n <= 10e6)
e cảm ơn mn ạ
Cần giúp đỡ thuật toán tìm đoạn con có ít nhất k phần tử mà có tổng lớn nhất
Dùng vòng lặp mà dò thôi. 
3 Likes
là sao bác! Bác giải thích rõ hơn đc ko ??
Theo mình thì bạn có thể làm như này:
- Sắp xếp dãy số theo thứ tự giảm dần
- Dùng vòng lặp để lấy k phần tử ra từ dãy số đã được sắp xếp
3 Likes
Hi Thái Dương An.
Tước tiên bạn tính tổng cộng dồn (bn = bn-1 + an với b1 = a1). Sau đó tìm kiếm cực tiểu gối trên các đoạn k phần tử (tìm min trên k phần tử đầu tiên trên b sau đó thêm 1 phần tử k + 1 và loại bỏ phần tử 0, cập nhật min mới). Sau đó với mỗi phần tử min bạn tìm max trong doạn từ nó đến min gần nhất. 2 cập min max có hiệu lớn nhất thì lớn nhất.
P/S Chém thê thôi.
4 Likes
Vậy là nát cái dãy số rồi còn gì
3 Likes
Là sao? Nghĩa là hơn k phần tử vẫn được?
3 Likes
5 năm kể từ khi tốt nghiệp c3 học code giờ mới suy nghĩ về một thuật toán :))
Bạn có thể xử lý như sau, độ phức tạp thì mình quên cách tính rồi 
Ban đầu đặt max, chỉ số đầu, chỉ số cuối.
Chạy vòng lặp từ 1 đến n
Vòng lặp từ 1 đến k
Cộng a[i] vào rồi so sánh với max
Nếu lớn hơn thì thay đổi chỉ số đầu, chỉ số cuối.
Rồi in ra chỉ số đầu, chỉ số cuối, max.
Có sai thì ae sữa đi nhé, mình đi phụ hồ tiếp đây:))
Vì ít nhất là k phần tử nên vòng lặp sau là từ k tới n nhé:v:
3 Likes
Sắp xếp thì nát rồi ấy bạn :))
1 Like
em mới học code =)))
1 Like
Làm vậy là đúng rồi, Độ phức tạp thì là O(kn). 
Nhưng bạn không nhất thiết phải lặp từ 1 đến n, chỉ cần từ 1 đến n - k + 1 là được rồi.
Vòng lặp thứ 2 thì từ i đến i + k - 1. (i là biến chạy của vòng 1).
2 Likes
mảng con có ít nhất k phần tử mà tổng lớn nhất thì là mảng n rồi mà.
#include <conio.h>
#include <iostream>
using namespace std;
void nhapmang(int a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << "a[" << i << "] = ";
cin >> a[i];
}
}
void xuatmang(int a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i];
}
}
int tinhtongkphantu(int a[], int n, int dodai, int phantudau)
{
int tong = 0;
for (int i = phantudau; i < phantudau + dodai; i++)
{
tong += a[i];
}
return tong;
}
int main()
{
int a[100];
int n;
cout << "nhap so phan tu mang n \n";
cin >> n;
nhapmang(a, n);
cout << "nhap gia tri k la \n";
int k;
cin >> k;
int max=0;
int kmax;
int imax;
for (int i = 0; i < n; i++)
{
for (int dodai = k; i+dodai-1 < n; dodai++)
{
if (tinhtongkphantu(a, n, dodai , i) > max)
{
max = tinhtongkphantu(a, n, dodai, i);
imax = i;
kmax = dodai;
}
}
}
cout << " tong max la ";
cout << max;
cout << " \ndo dai la ";
cout << kmax<<endl;
cout << "mang con max la ";
for(int i=imax; i<imax+kmax; i++)
{
cout << a[i] << "\t";
}
system("pause");
return 0;
}
1 Like
Số nguyên chứ ko phải số tự nhiên :))
Khổ, thế này thì dùng rolling sum còn nhanh hơn
3 Likes
Thớt dùng dequeue xem
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?