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


  • 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