Dãy con liên tiếp có tổng lớn nhất

Đề bài: Cho dãy số A, tìm và in ra vị trí bắt đầu, kết thúc của dãy con liên tiếp có tổng lớn nhất; và tổng lớn nhất đó

Input:
5
1 2 3 4 -5

Output:
1 4 10

Code C++:
Độ phức tạp O(N)

#include <iostream>
#include <utility>
using namespace std;

/*---------------------------*/

int main() {
    
    int n; cin >> n;
    long long sum = 0;
    long long ans = 0;
    int tracki = 1;
    pair<int,int> resIndex;
    for(int i = 1; i <= n; i++) {
        int v;
        cin >> v;
            
        sum += v;
            
        if (ans < sum ||
            (ans == sum /* && i-tracki > resIndex.se - resIndex.fi) */)) {
                ans = sum;
                resIndex.first = tracki;
                resIndex.second = i;
            }
            
        if (sum < 0) {
            sum = 0;
            tracki = i + 1;
        }
            
    }
    
    if (ans <= 0) cout << "Bad input";
    else cout << resIndex.first << " " << resIndex.second << ' ' << ans;

    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s