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

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;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *