Tìm dãy con liên tiếp không giảm có tổng lớn nhất

118
Lập trình C++

Bài toán. Tìm dãy con liên tiếp không giảm có tổng lớn nhất. Kết quả ghi ra tổng và liệt kê dãy các phần tử có tổng lớn nhất. Ví dụ:

DAYKT.INP

DAYKT.OUT

6

3 2 5 7 4 6

14

2 5 7

Code tham khảo:

#include <iostream>
using namespace std;

int main() {
    freopen("SUMDS.INP","r",stdin);
    freopen("SUMDS.OUT","w",stdout);
    int n, a[1000], b[1000], c[1000], d[1000];
    cin >> n;
    for(int i=0; i < n; i++) {
        cin >> a[i];
        b[i] = 1;
    }
    for(int i=n-1; i>0; i--) {
        if(a[i] >= a[i-1]) {
            b[i-1] += b[i];
        }
    }
    int i = 0;
    int k = 0;
    int m = 0;
    int index = 0;
    int sl = 0;
    while (i < n) {
        if(b[i] == 1) {
            c[k] = a[i];
            i++;
            if (m < c[k]) {
                m = c[k];
                index = i;
                sl = b[i];
            }
        }
        else {
            c[k] = 0;
            for(int j=i; j < i+b[i]; j++) {
                c[k] += a[j];
            }
            if (m < c[k]) {
                m = c[k];
                index = i;
                sl = b[i] + 1;
            }
            i += b[i];
        }
        k++;
    }
    for (i=0; i < k; i++) {
        if(m < c[i]) m = c[i];
    }
    cout << m << " " << endl;
    for (int i = index; i < sl; i++)
        cout << a[i] << " ";
    return 0;
}