Maximum Sum Circular Subarray
2020/5/16
問題概要
[1,-2,3,-2]のような配列が与えられる
これがリングバッファのようなデータ構造の時、部分配列の和の最大値を求めよ
解法
最初、累積和を使って$ O(N^2)で解こうとしたら、配列要素数が20,000程度のテストケースがあってTLE判定 直観的な数式付きで分かりやすい
以下は自分の理解のため書いてみたもの(数式は全然書き慣れてないのでぐちゃぐちゃ)
https://gyazo.com/e9928f64e3c0ec196736f8f1da1e23d0
以上で、通常の配列であれば$ O(N)で部分配列の最大和が求まることが分かった
今回は負の数もありうる環状の配列
以下を考慮すれば同じように時間計算量は$ O(N), 空間計算量は$ O(1)で解ける
全て負の数の場合
配列内の最大値の要素
それ以外の場合
配列の合計 - Kadaneで求めた部分配列の最小値
Kadaneで求めた部分配列の最大値
code:solution.cpp
#define all(v) (v).begin(),(v).end() using ll = long long;
class Solution {
public:
int maxSubarraySumCircular(vector<int>& A) {
if (A.size() < 3) {
auto iter = max_element(all(A));
return max(*iter, accumulate(all(A), 0));
}
// kadae algorithm's min & max
int min_num = INT_MAX, max_num = -INT_MAX;
int min_tmp = 0, max_tmp = 0;
// negative flag
bool negatives = true;
for (int a : A) {
if (a >= 0) negatives = false;
min_tmp = min(min_tmp+a, a);
max_tmp = max(max_tmp+a, a);
min_num = min(min_num, min_tmp);
max_num = max(max_num, max_tmp);
}
if (negatives) return *(max_element(all(A)));
return max(max_num, accumulate(all(A), 0)-min_num);
}
};