题解

问题理解

我们需要找到一个子数组（连续的子序列），使得该子数组的情感值之和乘以子数组中的最小情感值的乘积最大。这个乘积反映了该时期生活的“价值”。

解决思路

1. 问题分析：

   • 对于每个子数组，其价值为 sum(a[l..r]) * min(a[l..r])。
   • 直接枚举所有可能的子数组并计算其价值的时间复杂度为 $O(n^2)$，对于 $n \leq 100,000$ 来说是不可行的。

2. 优化思路：

   • 使用单调栈来高效地找到每个元素作为最小值时的最大子数组和。
   • 维护一个单调递增的栈，栈中存储的是数组的索引。对于每个元素，当它作为最小值时，找到其左右边界，使得该边界内的所有元素都大于或等于它。
   • 计算以当前元素为最小值的子数组的和，并更新最大价值及其对应的区间。

3. 算法步骤：

   • 计算前缀和数组 prefix_sum，用于快速计算子数组的和。
   • 使用单调栈遍历数组，对于每个元素，找到其作为最小值时的左右边界。
   • 计算以当前元素为最小值的子数组的价值，并更新最大价值及其对应的区间。

代码实现

以下是完整的 C++ 代码实现：

#include <iostream>
#include <vector>
#include <stack>
#include <climits>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);  // 使用 NULL 代替 nullptr 以确保兼容性

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<long long> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + a[i];
    }

    stack<int> s;
    long long max_value = 0;
    int best_l = 0, best_r = 0;

    for (int i = 0; i <= n; ++i) {
        while (!s.empty() && (i == n || a[s.top()] > a[i])) {
            int mid = s.top();
            s.pop();
            int left = s.empty() ? 0 : s.top() + 1;
            int right = i - 1;
            long long sum = prefix_sum[right + 1] - prefix_sum[left];
            long long current_value = sum * a[mid];
            if (current_value > max_value) {
                max_value = current_value;
                best_l = left + 1;
                best_r = right + 1;
            }
        }
        s.push(i);
    }

    cout << max_value << '\n';
    cout << best_l << ' ' << best_r << '\n';

    return 0;
}

代码解释

1. 输入处理：

   • 读取数组长度 n 和情感值数组 a。
   • 计算前缀和数组 prefix_sum，用于快速计算子数组的和。

2. 单调栈处理：

   • 使用单调栈 s 来维护一个单调递增的序列。
   • 遍历数组，对于每个元素 a[i]，如果它小于栈顶元素，则弹出栈顶元素，并计算以该栈顶元素为最小值的子数组的价值。
   • 更新最大价值 max_value 及其对应的区间 [best_l, best_r]。

3. 输出结果：

   • 输出最大价值 max_value 和对应的区间 [best_l, best_r]。

复杂度分析

• 时间复杂度：$O(n)$，每个元素最多入栈和出栈一次。
• 空间复杂度：$O(n)$，用于存储前缀和数组和单调栈。