Tổng dãy con

Xem PDF




Thời gian:
Python 3 3.0s
Bộ nhớ:
Python 3 260M

Tác giả:
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


  • 8
    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)\)\((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;
    }
    

    • 0
      huanhoang2004    9:42 a.m. 16 Tháng 6, 2020

      bài này không hỗ trợ C++ :<


      • 6
        cuom1999    9:58 a.m. 16 Tháng 6, 2020

        Đã sửa lỗi. Xin lỗi bạn

      3 bình luận nữa