C++ Coding Test Course, Making the Maximum Value by Grouping Numbers

Problem Description

You need to combine the given integers appropriately to create one maximum value while receiving multiple integers. The integers follow these rules:

• Integers can include negative and positive values, and 0 also exists.
• Multiplying a negative with another negative creates a positive, allowing for larger numbers to be made.
• Positive numbers should only be multiplied with numbers greater than 1, otherwise, their sum will be larger. 1 is used for addition.
• 0 does not affect the maximum value but can be multiplied by negative numbers.

For example, if the given integers are {1, 2, 0, -1, -2}, the maximum value would be
(2 * 1) + (0) + ((-1) * (-2)) = 2 + 0 + 2 = 4.

Input

The first line contains an integer N (1 ≤ N ≤ 100,000),
and the second line contains N integers arr[i] (-1,000 ≤ arr[i] ≤ 1,000).

Output

Output the maximum value of the integers in one line.

Problem Solving Process

Step 1: Reading Input

Read the input integers and convert them into a format that the computer can understand. In C++,
vector is used to store the integers.
All values are processed by storing them in one list.

Step 2: Separating Integers

First, separate the integers into positive, negative, and 0. This allows for various cases
to be handled efficiently. The goal is to group negative numbers to create positives,
and combine positives to form the maximum value.

Step 3: Handling Positives

Sort the list of positive numbers and start multiplying the larger values at the end first. Only
values greater than 1 should be combined, so it’s best to group with 1.

Step 4: Handling Negatives

Handle negatives by combining them in pairs to create the maximum value. For example,
multiplying two negatives yields a positive, so they should be combined.

Step 5: Calculating and Outputting the Result

Ultimately, store the maximum value obtained through all combinations and output it.
This process can be easily implemented using the C++ code below.

Code Example

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

                using namespace std;

                int main() {
                    int N;
                    cin >> N;

                    vector arr(N);
                    vector positive;
                    vector negative;

                    for (int i = 0; i < N; i++) {
                        cin >> arr[i];
                        if (arr[i] > 0) positive.push_back(arr[i]);
                        else if (arr[i] < 0) negative.push_back(arr[i]);
                    }

                    sort(positive.rbegin(), positive.rend());
                    sort(negative.begin(), negative.end());

                    long long result = 0;

                    for (int i = 0; i < positive.size(); i += 2) {
                        if (i + 1 < positive.size()) {
                            result += positive[i] * positive[i + 1];
                        } else {
                            result += positive[i];
                        }
                    }

                    for (int i = 0; i < negative.size(); i += 2) {
                        if (i + 1 < negative.size()) {
                            result += negative[i] * negative[i + 1];
                        }
                    }

                    cout << result << endl;

                    return 0;
                }
            
        

Conclusion

This problem is an important algorithmic challenge of creating maximum value from the given integers.
The approach above helps to effectively solve the problem.
The key is classifying integers and deriving results through appropriate mathematical operations. Additionally, learning to write code using C++’s STL can be applied to other problems as well.