Tổng mảng con tròn lớn nhất trong C++

Cho mảng tròn C được biểu diễn bởi mảng A, tìm tổng lớn nhất của một mảng con không rỗng của C. Mảng con chỉ có thể chứa mỗi phần tử của A tối đa một lần. Ví dụ: [1,-2,3,-2] → 3 (mảng con [3]).

Giải thuật

• n := kích thước mảng
• Tạo các mảng leftSum, leftSumMax, rightSum, rightSumMax kích thước n.
• leftSum[0] = v[0], leftSumMax[0] = max(0, v[0]).
• Với i từ 1 đến n-1:
  • leftSum[i] = leftSum[i-1] + v[i]
  • leftSumMax[i] = max(leftSum[i], leftSumMax[i-1])
• rightSum[n-1] = v[n-1], rightSumMax[n-1] = max(0, v[n-1]).
• Với i từ n-2 xuống 0:
  • rightSum[i] = rightSum[i+1] + v[i]
  • rightSumMax[i] = max(rightSumMax[i+1], rightSum[i])
• leftAns = leftSum[0] + rightSumMax[1].
• Với i từ 1 đến n-2: leftAns = max(leftAns, leftSum[i] + rightSumMax[i+1]).
• rightAns = rightSum[n-1] + leftSumMax[n-2].
• Với i từ n-2 xuống 1: rightAns = max(rightAns, rightSum[i] + leftSumMax[i-1]).
• Áp dụng thuật toán Kadane tìm tổng mảng con lớn nhất không tròn (kadane).
• Trả về max(leftAns, rightAns, kadane).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& v) {
        int n = v.size();
        vector<int> leftSum(n), leftSumMax(n), rightSum(n), rightSumMax(n);
        leftSum[0] = v[0];
        leftSumMax[0] = max(0, v[0]);
        for (int i = 1; i < n; i++) {
            leftSum[i] = leftSum[i-1] + v[i];
            leftSumMax[i] = max(leftSum[i], leftSumMax[i-1]);
        }
        rightSum[n-1] = v[n-1];
        rightSumMax[n-1] = max(0, v[n-1]);
        for (int i = n-2; i >= 0; i--) {
            rightSum[i] = rightSum[i+1] + v[i];
            rightSumMax[i] = max(rightSumMax[i+1], rightSum[i]);
        }
        int leftAns = leftSum[0] + rightSumMax[1];
        for (int i = 1; i < n-1; i++)
            leftAns = max(leftAns, leftSum[i] + rightSumMax[i+1]);
        int rightAns = rightSum[n-1] + leftSumMax[n-2];
        for (int i = n-2; i >= 1; i--)
            rightAns = max(rightAns, rightSum[i] + leftSumMax[i-1]);
        int curr = v[0], kadane = v[0];
        for (int i = 1; i < n; i++) {
            curr = max(v[i], curr + v[i]);
            kadane = max(kadane, curr);
        }
        return max(leftAns, max(rightAns, kadane));
    }
};

Đầu vào

[1,-2,3,-2]

Đầu ra

3