Tổng dãy con

Xem PDF
Thời gian:
Python 3 3.0s
Bộ nhớ:
Python 3 260M
Tác giả:
admin
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên gồm \(N\) phần tử. Tìm:

  • Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp)
  • Dãy con gồm các phần tử liên tiếp có tổng lớn nhất.

Input

  • Gồm nhiều test, dòng đầu tiên là số lượng test \(T\) \((1≤T≤10)\)
  • Mỗi bộ test gồm hai dòng:
    • Dòng đầu là số nguyên dương \(N\) là số lượng phần tử của dãy \((1≤N≤10^5)\)
    • Dòng tiếp theo gồm \(N\) số nguyên trong khoảng \([−10^4,10^4]\)

Output

  • Với mỗi bộ test, in ra trên một dòng, hai số là hai tổng theo yêu cầu.

Example

Test 1

Input 
2
3
4 4 2
5
3 3 -2 3 -4
Output 
10 10
9 7

Bình luận


  • 1
    pa_ldk    2:51 p.m. 9 Tháng 5, 2024

    include <bits/stdc++.h>

    using namespace std;
    const int N = 1e5 + 5;
    int a[N];
    int s1(int n) {
    int res = 0;
    for (int i = 0; i < n; i++) {
    if (a[i] > 0) {
    res += a[i];
    }
    }
    if(res == 0){
    res = *max_element(a, a + n);
    }
    return res;
    }
    int s2(int n) {
    int s = a[0];
    int res = a[0];
    for (int i = 1; i < n; i++) {
    res = max(a[i], res + a[i]);
    s = max(s, res);
    }
    return s;
    }
    int main() {
    int t;
    cin >> t;
    while (t--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
    cin >> a[i];
    }
    cout << s1(n) << " " << s2(n) << endl;
    }
    return 0;
    }


    • 0
      dbthuan208    11:27 p.m. 29 Tháng 6, 2023

      q1 bình thường
      q2 kadane
      k bt cho vào spoiler ntn admin cho giùm 😊


      • 0
        Truongkhaiminh    12:43 p.m. 4 Tháng 11, 2020

        cau lenh query dung thu vien j a

        1 phản hồi

        • 7
          SPyofgame    3:52 p.m. 15 Tháng 6, 2020

          Spoiler Alert

          Hint 1

          • Tìm dãy con có tổng lớn nhất

          Ý tưởng cơ bản: Thử tất cả các dãy \(a_i, a_j, ...\) và tìm dãy có tổng lớn nhất

          • Tìm đoạn con có tổng lớn nhất

          Ý tưởng cơ bản: Thử tất các các đoạn \((i, j)\) và \((i \leq j)\) và tìm đoạn có tổng lớn nhất

          Hint 2

          • Tìm dãy con tổng lớn nhất

          Gọi \(sum1\) là tổng ở hiện tại

          Nhận xét rằng \(sum1 + x < sum1\) khi \(x < 0\)

          Nhận xét rằng \(sum1 + x \geq sum1\) khi \(x \geq 0\)

          • Tìm đoạn con có tổng lớn nhất

          Gọi \(curr\) là giá trị lớn nhất đến hiện tại

          Gọi \(sum2\) lá giá trị cực đại của \(curr\)

          Nhận xét rằng \(curr + x < x\) khi \(curr < 0\)

          Nhận xét rằng \(curr + x \geq x\) khi \(curr \geq 0\)

          Hint 3

          • Tìm dãy con tổng lớn nhất

          Trong trường hợp mảng chí toàn âm: Ta tìm số âm lớn nhất

          Trong trường hợp mảng có số không âm: Ta tính tổng tất cả các số không âm

          • Tìm đoạn con có tổng lớn nhất

          Trong trường hợp \(curr\) âm, ta thay \(curr = x\)

          Trong trường hợp \(curr\) dương, ta thêm \(curr\) đại lượng \(x\)

          \(sum2 = max(curr)\) tại mọi thời điểm

          Hint 4

          • Tìm dãy con tổng lớn nhất

          \(sum1 = max(sum1, max(sum1 + temp, temp));\)

          • Tìm đoạn con có tổng lớn nhất [Kadane Algorithm]

          \(curr = max(temp, curr + temp);\)

          \(sum2 = max(sum2, curr);\)

          Reference AC code | \(O(n)\) time | \(O(1)\) auxiliary space | Online Solving, Greedy, DP

          C++
          int query()
{
    int sum1 = -INF;
    int sum2 = -INF, curr = 0;
    for (int n = readInt(); n--; ) {
        int temp;
        cin >> temp;
        sum1 = max(sum1, max(sum1 + temp, temp));
        curr = max(temp, curr + temp);
        sum2 = max(sum2, curr);
    }

    cout << sum1 << ' ' << sum2 << '\n';
    return 0;
}
          1 phản hồi