leetcode思路个人版c++求解a

Question

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// 计算当前数组的总和
int calculateTotalSum(const vector<int>& arr) {
    int total = 0;
    for (int num : arr) {
        total += num;
    }
    return total;
}

// 计算前缀和
vector<int> computePrefixSum(const vector<int>& arr) {
    int m = arr.size();
    vector<int> prefixSum(m + 1, 0);
    for (int i = 0; i < m; ++i) {
        prefixSum[i + 1] = prefixSum[i] + arr[i];
    }
    return prefixSum;
}

// 计算长度为n的子数组的和
vector<int> getSubarraySums(const vector<int>& prefixSum, int n) {
    int m = prefixSum.size() - 1;
    vector<int> subarraySums(m - n + 1);
    for (int i = 0; i <= m - n; ++i) {
        subarraySums[i] = prefixSum[i + n] - prefixSum[i];
    }
    return subarraySums;
}

// 使用动态规划更新最大和
int maxSumAfterOperations(int n, vector<int>& arr) {
    int m = arr.size();
    vector<int> prefixSum = computePrefixSum(arr);
    vector<int> subarraySums = getSubarraySums(prefixSum, n);

    int initialSum = calculateTotalSum(arr);
    int maxSum = initialSum;

    // 贪心策略：尽可能多地取反以提高总和
    // 这里我们直接计算增量
    while (true) {
        int maxIncrement = INT_MIN;
        int bestStartIndex = -1;
        for (int i = 0; i <= m - n; ++i) {
            int currentSum = subarraySums[i];
            int increment = -2 * currentSum;
            if (increment > maxIncrement) {
                maxIncrement = increment;
                bestStartIndex = i;
            }
        }
        
        if (maxIncrement <= 0) break; // 如果增量小于等于0，则停止
        
        // 更新总和
        maxSum += maxIncrement;

        // 对选择的子数组进行取反
        for (int i = bestStartIndex; i < bestStartIndex + n; ++i) {
            arr[i] = -arr[i];
        }
        
        // 更新前缀和和子数组和
        prefixSum = computePrefixSum(arr);
        subarraySums = getSubarraySums(prefixSum, n);
    }

    return maxSum;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(2 * n - 1);
    for (int i = 0; i < 2 * n - 1; ++i) {
        cin >> arr[i];
    }

    int result = maxSumAfterOperations(n, arr);
    cout << result << endl;

    return 0;
}

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

上述C++程序实现的主要功能是计算一组数通过一些特定的运算后得到的结果。该程序具体的操作过程如下：

1. 首先，程序从标准输入读取一个整数n，然后创建一个长度为2n-1的整数数组arr。接着，程序读取这个数组的所有元素。
2. 然后，程序计算数组中所有元素的绝对值的总和（初始的和）。这是通过将数组的每个元素取绝对值并累加得到的。
3. 之后，程序找出数组中的最小绝对值。这是通过遍历数组并使用min_element函数实现的，该函数使用了一个lambda函数来比较两个元素的绝对值大小。
4. 接着，程序计算数组中负数的数量（使用count_if函数）。这是一个条件判断，判断数组中哪些元素是负数。
5. 最后，如果负数的数量是奇数（即不是偶数），则将从初始和中减去最小的绝对值的两倍。这是因为在所有元素都取绝对值并相加后，如果负数的数量是奇数，那么总和可能会因为最小的负数被抵消而偏小，因此需要调整总和的大小以确保结果正确。在这种情况下，我们将总和减去两个最小绝对值的值以补偿这一偏差。最后，输出调整后的总和。

这个程序可能用于解决一些涉及绝对值求和和最小绝对值的问题，特别是在处理包含正负数的数组时。然而，由于代码片段并没有提供具体的上下文或问题背景，因此无法确定这个程序具体是解决哪种问题的。