与えられた配列から、部分配列の和の絶対値の最大値を求めます。部分配列は空でも構いません。

方法1

最大部分配列の和と最小部分配列の和を別々に動的計画法で計算します。その後、これらの値の絶対値の最大値を求めます。

考え方

• max_sum_ending_at[i]: nums[i]で終わる部分配列の中で最大の和
• min_sum_ending_at[i]: nums[i]で終わる部分配列の中で最小の和

コード

const int MAX_N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> max_sum_ending_at(n), min_sum_ending_at(n);
        int result = 0;

        max_sum_ending_at[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            max_sum_ending_at[i] = max(max_sum_ending_at[i - 1], 0) + nums[i];
            result = max(result, max_sum_ending_at[i]);
        }

        min_sum_ending_at[0] = nums[0];
        result = max(result, abs(min_sum_ending_at[0]));
        for (int i = 1; i < n; ++i) {
            min_sum_ending_at[i] = min(min_sum_ending_at[i - 1], 0) + nums[i];
            result = max(result, abs(min_sum_ending_at[i]));
        }

        return result;
    }
};

空間効率の高いバージョン

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int n = nums.size();
        int result = abs(nums[0]);

        int current_max = nums[0];
        for (int i = 1; i < n; ++i) {
            current_max = max(current_max, 0) + nums[i];
            result = max(result, current_max);
        }

        int current_min = nums[0];
        for (int i = 1; i < n; ++i) {
            current_min = min(current_min, 0) + nums[i];
            result = max(result, abs(current_min));
        }

        return result;
    }
};

方法2

累積和を使用して、各要素を部分配列の最後尾として取り上げることで、全ての部分配列の和の最大値と最小値を求めます。

考え方

各ポイントを最後尾として、その前にある部分配列の和の最小値や最大値を考えます。
これにより、[j+1, i]の部分配列の和は[0, i]の中での部分配列の和の最大値または最小値となります。
その後、これらの値の絶対値の最大値を求めます。

コード

#include <set>

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int n = nums.size();
        set<int> prefix_sums;
        prefix_sums.insert(0);

        int cumulative_sum = 0, result = 0;
        for (int i = 0; i < n; ++i) {
            cumulative_sum += nums[i];
            result = max({result, abs(cumulative_sum - *prefix_sums.begin()), abs(cumulative_sum - *prefix_sums.rbegin())});
            prefix_sums.insert(cumulative_sum);
        }
        return result;
    }
};