Tối ưu code tính tổng lớn nhất của dãy con k phần tử liên tiếp của mảng

[Anh_Duc3 (Anh Duc)]

Cho n số nguyên a[1], a[2],…, a[n] và số nguyên k (-10000 ≤ a[i] ≤ 10000, 1 ≤ n ≤ 100000, 1 ≤ k ≤ n). Hãy tìm tổng lớn nhất của k số nguyên liên tiếp a[i]+a[i+1]+ . . . +a[i+k-1] (i+k-1 ≤ n).

Mọi người giúp em tối ưu chương trình được không ạ?

#include <bits/stdc++.h>

using namespace std;
int n,k,a[100001],t=0,e=0;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n-k+1;i++)
    {
        t=0;
        for(int j=i;j<=i+k-1;j++)
        {
            t=t+a[j];
        }
        if(t>e)
            e=t;
    }
    cout<<e;
    return 0;
}

[dtran]

a[1], a[2],…, a[n] nhập vào có đảm bảo có k số nguyên liên tiếp không?
Bạn nên sắp xếp mảng a[] theo thứ tự từ lớn -> bé.
Sau đó cứ vòng for chạy từ a[0] tới a[k-1] sẽ dc tổng lớn nhất nếu có k số nguyên liên tiếp.
Nếu không có thì sẽ lấy từ a[x+1] tới a[k-1] với x là ví trí tại đó mà số nguyên ấy k liên tục.

[907pqv (Violet)]

Cách tính của bạn hiện tại là với mỗi phần tử a[i] của mảng thì tính tổng k phần tử liên tiếp sau nó a[i] + a[i+1] +...+ a[i+k-1] .Ở bước tính tổng này tốn 1 vòng for, do đó, độ phức tạp hiện tại là O(n^2).

Thay vì vậy bạn có thể tính tổng này chỉ trong O(1) bằng cách lấy tổng ở bước trước là S = a[i-1] + a[i] + ....+ a[i+k-2] trừ cho a[i-1] rồi cộng a[i+k-1]

Ví dụ:
1 2 3 4 2 5 1 0 2 với k = 3
[1 2 3] 4 2 5 1 0 2 ==> S = 6
1 [2 3 4] 2 5 1 0 2 ==> S = 6 -1 + 4 = 9
1 2 [3 4 2] 5 1 0 2 ==> S = 9- 2 + 2 = 9
1 2 3 [4 2 5] 1 0 2 ==> S = 9- 3 + 5 = 11
…
cứ dịch chuyển cặp ngoặc vuông đi 1 đơn vị như vậy.
Độ phức tạp: O(n)

[rogp10]

Đã liên tiếp rồi còn sắp xếp gì được bạn

[Anh_Duc3 (Anh Duc)]

Cảm ơn anh nha em nộp lại nó không bị quá giới hạn thời gian nữa nhưng nó vẫn sai 1 test

[Chi_Khiem_Nguyen (Chí Khiêm Nguyễn)]

sử dụng mãng cộng dồn nha bn

#include <bits/stdc++.h>
using namespace std;
const int Max=1e6+1;
int n,k;
int a[Max];

int main(){
	ios::sync_with_stdio(0);
	cin.tie();
	cin>>n>>k;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=a[i-1];
	}
	int maxsimum=0;
	for (int i=1;i<=n-k+1;i++){
		int sum=a[k+i-1]-a[i-1];
		cout<<sum<<" ";
		if (maxsimum<sum) maxsimum=sum;
	}
	cout<<maxsimum;
	return 0;
}