求最大乘积和的C++算法代码错误修复请求

给定n个整数，可选择将两个数相乘或保留原数，需计算所有运算后数值相加的最大值。

测试示例 #

• 输入：数组长度9，元素为-1 -8 2 1 3 6 -5 0 1，正确输出为62，计算方式：62=-8×-5+0×-1+6×3+2+1+1
• 输入数组7 4 1 2 5 3 1 9 0，正确输出为91
• 输入数组-13 7 -12 13 -8 4 12 7 15 6 -2 10 9 15 4 1 -15，正确输出为838

本人实现的代码 #

#include <iostream>
#include "sop.h"
using namespace std;

sop::sop() {
    this->num = 0;
    this->array = NULL;
}

sop::sop(int* a, int n) {
    this->num = n;
    this->array = new int[n];
    for (int i = 0; i < n; i++) this->array[i] = a[i];
}

sop::~sop() {
    if (this->array) {
        delete[] this->array;
    }
    this->num = 0;
    this->array = NULL;
}

void sop::printArray(void) {
    if (!this->num)  return;
    for (int i = 0; i < num; i++) cout << array[i] << "  ";
    cout << endl;
}

int myMax(int a, int b) {
    return (a > b) ? a : b;
}

int sop::maxSOP() {
    if (num == 0) return 0;
    if (num == 1) return array[0];

    int maxSum = array[0]; // Initialize maxSum to the first element
    int currentMax = array[0]; // Initialize currentMax to the first element

    for (int i = 1; i < num; i++) {
        int temp = currentMax; // Store the previous currentMax

        // Calculate the current maximum product including the current element
        currentMax = myMax(array[i], myMax(currentMax * array[i], temp * array[i]));

        // Update maxSum with the maximum of maxSum and currentMax
        maxSum = myMax(maxSum, currentMax);
    }

    return maxSum;
}

其中maxSOP和myMax为核心实现函数。

问题 #

针对第一组测试用例，上述代码输出结果为288，而非正确值62，请求帮忙修复该代码。

辅助文件 #

otherfile.cpp

#include <iostream>
#include <fstream>
#include "sop.h"
using namespace std;

int main(int argc, char* argv[]) {
    int i = 0;
    int num = 0;
    int* array = NULL;
    ifstream fin;
    sop* _sop = NULL;

    if (argc > 1) {
        fin.open(argv[1]);
        if (!fin.is_open()) {
            cerr << "File " << argv[1] << " does not exist!" << endl;
            exit(0);
        }
        fin >> num;
        array = new int[num];
        for (i = 0;i < num;i++)        fin >> array[i];
        fin.close();
    }
    else {
        cin >> num;
        array = new int[num];
        for (i = 0;i < num;i++)        cin >> array[i];
    }

    _sop = new sop(array, num);
    cout << "Input array: ";
    _sop->printArray();
    cout << "Maximum sum of products = " << _sop->maxSOP() << endl;
    delete _sop;
    if (array)       delete[] array;
    array = NULL;
    return 0;
}

otherheader.h

#include <iostream>
#include <fstream>
#include "sop.h"
using namespace std;

int main(int argc, char* argv[]) {
    int i = 0;
    int num = 0;
    int* array = NULL;
    ifstream fin;
    sop* _sop = NULL;

    if (argc > 1) {
        fin.open(argv[1]);
        if (!fin.is_open()) {
            cerr << "File " << argv[1] << " does not exist!" << endl;
            exit(0);
        }
        fin >> num;
        array = new int[num];
        for (i = 0;i < num;i++)        fin >> array[i];
        fin.close();
    }
    else {
        cin >> num;
        array = new int[num];
        for (i = 0;i < num;i++)        cin >> array[i];
    }

    _sop = new sop(array, num);
    cout << "Input array: ";
    _sop->printArray();
    cout << "Maximum sum of products = " << _sop->maxSOP() << endl;
    delete _sop;
    if (array)       delete[] array;
    array = NULL;
    return 0;
}

问题分析与修复 #

错误原因 #

你的代码实现的是连续子数组的最大乘积逻辑，比如第一组测试用例中，它计算出的288是-8*2*1*3*6*-5的结果，但题目要求的是将数组元素任意分组（每组最多两个元素），所有组的运算结果（单个元素保留原值，两个元素相乘）之和的最大值，两者的核心逻辑完全不同。

修复思路 #

要解决这个问题，需要针对正负数值的特性进行分组策略优化：

1. 负数两两相乘得到正数，优先配对绝对值最大的负数
2. 正数中，当两个数都大于1时，相乘的结果大于两数之和；若包含1，则直接相加更优
3. 单个负数若和零配对，结果为0，比单独取负数更划算

修复后的代码 #

首先需要在sop.cpp顶部添加<algorithm>头文件用于数组排序：

#include <iostream>
#include <algorithm> // 添加排序所需头文件
#include "sop.h"
using namespace std;

然后替换maxSOP函数：

int sop::maxSOP() {
    if (num == 0) return 0;
    if (num == 1) return array[0];

    // 复制数组并排序，方便分组处理
    int* sortedArr = new int[num];
    for (int i = 0; i < num; i++) {
        sortedArr[i] = array[i];
    }
    sort(sortedArr, sortedArr + num);

    int total = 0;
    int left = 0;
    int right = num - 1;

    // 处理负数：两两配对相乘（负负得正）
    while (left < right && sortedArr[left] < 0 && sortedArr[left + 1] < 0) {
        total += sortedArr[left] * sortedArr[left + 1];
        left += 2;
    }

    // 处理正数：从右往左，优先配对大于1的数相乘
    while (right >= left && sortedArr[right] > 1) {
        if (right > left && sortedArr[right - 1] > 1) {
            total += sortedArr[right] * sortedArr[right - 1];
            right -= 2;
        } else {
            total += sortedArr[right];
            right--;
        }
    }

    // 处理剩余元素（可能是单个负数、0、1）
    while (right >= left) {
        // 若剩余单个负数，且存在0，则选择加0而非负数
        if (sortedArr[left] < 0) {
            bool hasZero = false;
            for (int i = left; i <= right; i++) {
                if (sortedArr[i] == 0) {
                    hasZero = true;
                    break;
                }
            }
            if (hasZero) {
                left++; // 跳过负数，后续会处理0
            } else {
                total += sortedArr[left];
                left++;
            }
        } else {
            total += sortedArr[left];
            left++;
        }
    }

    delete[] sortedArr;
    return total;
}

验证结果 #

• 第一组测试用例排序后为-8,-5,-1,0,1,1,2,3,6，计算过程：-8*-5=40 + 6*3=18 + 2+1+1+0 = 62，符合预期
• 第二组测试用例计算结果为91，第三组为838，均符合要求

内容的提问来源于stack exchange，提问作者noroong