当给定 n 个整数时，您可以将两个数字相乘或保持原样。我编写了一个算法来查找所有值相加的最大值。
例如输入为：
9（数组长度） -1 -8 2 1 3 6 -5 0 1
输出需要是62：
62=-8x-5+0x-1+6x3+2+1+1
如果数组是
7 4 1 2 5 3 1 9 0-13 7 -12 13 -8 4 12 7 15 6 -2 10 9 15 4 1 -15我的代码是这样的：
#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;
}
maxSOPmyMax在这段代码中，结果是288，而不是62。我不知道为什么。您能修复这个代码吗？我将向您展示其他可以帮助您修复此代码的文件。
其他文件.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;
}
你不能对数组进行排序吗？
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
int MaxProductSum(std::vector<int>& nums) {
// Use the correct size type to avoid narrowing conversion warnings
std::vector<int>::size_type n = nums.size();
// Sort the array to arrange negative numbers in the front
std::sort(nums.begin(), nums.end());
int sum = 0;
std::vector<int>::size_type i = 0;
// Process negative numbers and zeros from the start
while (i < n - 1 && nums[i] < 0) {
if (nums[i + 1] <= 0) { // Multiply negatives together
sum += nums[i] * nums[i + 1];
i += 2;
} else { // If there's an odd number of negatives, handle the last one
if (nums[i + 1] == 0) { // Nullify the negative with zero
i += 2; // Skip the zero as well
} else {
sum += nums[i]; // Add the single negative number
i++;
}
}
}
// If only one negative number is left in the middle, add it
if (i == n - 1 && nums[i] < 0) {
sum += nums[i];
++i; // Move past the negative number
}
// Process positive numbers from the end
for (std::vector<int>::size_type j = n - 1; j >= i && nums[j] > 0; --j) {
if (j == i) { // Only one positive number left, add it
sum += nums[j];
break;
}
if (j > i && nums[j] * nums[j - 1] > nums[j] + nums[j - 1]) {
sum += nums[j] * nums[j - 1]; // Multiply if it's beneficial
--j; // Skip the next number as it's been paired
} else {
sum += nums[j]; // Add if multiplying is not beneficial
}
}
// Add the zero if it's left at the end
if (i == n - 1 && nums[i] == 0) {
sum += nums[i];
}
return sum;
}
template <typename T>
std::string VectorToString(const std::vector<T>& vec) {
std::ostringstream oss;
oss << '[';
for (size_t i = 0; i < vec.size(); ++i) {
oss << vec[i];
if (i < vec.size() - 1) {
oss << ", ";
}
}
oss << ']';
return oss.str();
}
int main() {
std::vector<int> test_case1 = {-1, -8, 2, 1, 3, 6, -5, 0, 1};
std::vector<int> test_case2 = {7, 4, 1, 2, 5, 3, 1, 9, 0};
std::vector<int> test_case3 = {-13, 7, -12, 13, -8, 4, 12, 7, 15, 6, -2, 10, 9, 15, 4, 1, -15};
std::cout << "MaxProductSum of " << VectorToString(test_case1) << ": " << MaxProductSum(test_case1) << '\n';
std::cout << "MaxProductSum of " << VectorToString(test_case2) << ": " << MaxProductSum(test_case2) << '\n';
std::cout << "MaxProductSum of " << VectorToString(test_case3) << ": " << MaxProductSum(test_case3) << '\n';
return 0;
}
输出：
MaxProductSum of [-1, -8, 2, 1, 3, 6, -5, 0, 1]: 62
MaxProductSum of [7, 4, 1, 2, 5, 3, 1, 9, 0]: 91
MaxProductSum of [-13, 7, -12, 13, -8, 4, 12, 7, 15, 6, -2, 10, 9, 15, 4, 1, -15]: 838