CF 1024805 - Максимальное произведение
We have a sequence of positive numbers. We need to choose one position where the sequence is cut into two non-empty consecutive parts. The value of a part is the sum of its elements, and the score of a cut is the product of the two resulting sums.
Rating: -
Tags: -
Solve time: 3m 16s
Verified: yes
Solution
Problem Understanding
We have a sequence of positive numbers. We need to choose one position where the sequence is cut into two non-empty consecutive parts. The value of a part is the sum of its elements, and the score of a cut is the product of the two resulting sums. The task is to output the position after which the cut should be made so that this product is as large as possible. If several positions give the same maximum value, any of them is accepted.
The array can contain up to $2 \cdot 10^5$ elements, and each element can be as large as $10^9$. A solution that tries every pair of borders or recomputes sums for every possible cut would quickly exceed the available time. Even $O(n^2)$ operations would mean around $4 \cdot 10^{10}$ checks in the largest case, which is far beyond what is practical. We need a linear or close to linear approach.
A common mistake is to think that the largest element should determine the cut. The objective depends on sums of groups, not individual values. Another mistake is forgetting that the answer is an index, not the maximum product itself.
Consider the array:
3
1 2 3
The correct output is:
2
Cutting after the second element gives sums $1+2=3$ and $3$, producing $9$. Cutting after the first element gives $1\cdot5=5$. A solution that only checks the largest element would not capture this.
Another edge case is an array where several cuts are equally good:
4
1 1 1 1
The correct output can be any of:
1
2
3
Every cut creates products $1\cdot3$, $2\cdot2$, or $3\cdot1$, so only the middle cut is actually optimal here. A careless implementation that assumes the first maximum encountered is always acceptable must still correctly update the answer logic.
A more relevant boundary case is when the best cut is very close to an end:
2
5 7
The only possible answer is:
1
There is no valid cut after the second element because both parts must be non-empty.
Approaches
The direct approach is to try every possible cut. For a cut after position $i$, we compute the sum of the left part and the sum of the right part, multiply them, and keep the best position. This is correct because every possible answer is checked. If sums are calculated from scratch for every position, the complexity is $O(n^2)$, because there are $n-1$ possible cuts and each calculation may scan many elements. With $n=200000$, this becomes approximately $4\cdot10^{10}$ additions.
The first improvement is to observe that all cuts share the same information. The total sum of the whole array never changes. If the sum of the left part is $x$, then the right part is simply $S-x$, where $S$ is the total sum. The product becomes:
$$x(S-x)$$
Now the problem is no longer about two independent sums. We only need to know the prefix sum after each position and find the value that maximizes the expression.
The function $x(S-x)$ is a parabola. Its maximum is reached when $x$ is as close as possible to $S/2$. Since all array elements are positive, prefix sums only increase as we move through the array. We can scan from left to right and compare each prefix sum with the best value seen so far.
The brute-force method works because it examines every possible partition. It fails because it repeatedly computes information that is already contained in previous cuts. The observation about the fixed total sum reduces the entire problem to one pass over the array.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Too slow |
| Optimal | O(n) | O(1) | Accepted |
Algorithm Walkthrough
- Compute the sum of all elements in the array. This value represents the combined weight of both parts for every possible cut.
- Traverse the array while maintaining the current prefix sum. After processing position $i$, this prefix sum is the weight of the left part if we cut after $i$.
- For each possible cut, calculate the product of the prefix sum and the remaining suffix sum. Compare it with the best product found so far, and store the position if it improves the answer.
- Output the stored position after the traversal finishes. Every possible non-empty left part has been considered exactly once.
Why it works:
For any cut, the two resulting weights always add up to the same total sum $S$. The score is determined only by the left weight $x$, because the right weight is $S-x$. During the scan, every possible value of $x$ produced by a valid cut is examined. Since the algorithm compares the product for every possible cut, the stored position must correspond to a maximum product.
Python Solution
import sys
input = sys.stdin.readline
def solve():
n = int(input())
a = list(map(int, input().split()))
total = sum(a)
best_product = -1
answer = 1
prefix = 0
for i in range(n - 1):
prefix += a[i]
product = prefix * (total - prefix)
if product > best_product:
best_product = product
answer = i + 1
print(answer)
if __name__ == "__main__":
solve()
The code first calculates the total array sum once. Python integers can handle the large products safely because the maximum possible product is around $10^{28}$.
The loop stops at n - 1 because the last element cannot be the end of the left part. Including it would leave an empty right part, which is not allowed.
The prefix sum is updated before calculating the product because the current index represents the element included in the left segment. The stored answer uses i + 1 because the problem asks for the position in one-based indexing.
The comparison uses only > rather than >=. When multiple cuts have the same product, keeping the first one is valid.
Worked Examples
For the input:
3
1 2 3
the execution is:
| Position | Prefix sum | Suffix sum | Product | Best answer |
|---|---|---|---|---|
| 1 | 1 | 5 | 5 | 1 |
| 2 | 3 | 3 | 9 | 2 |
The scan checks both valid cuts. The second cut gives the larger product, so the answer is position 2.
For the input:
5
10 1 1 1 10
the execution is:
| Position | Prefix sum | Suffix sum | Product | Best answer |
|---|---|---|---|---|
| 1 | 10 | 13 | 130 | 1 |
| 2 | 11 | 12 | 132 | 2 |
| 3 | 12 | 11 | 132 | 2 |
| 4 | 13 | 10 | 130 | 2 |
The maximum occurs twice. The algorithm keeps the first occurrence because both answers are valid.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Every array element is processed once |
| Space | O(1) | Only sums and the answer position are stored |
The linear complexity is suitable for $n=2\cdot10^5$. The algorithm avoids storing prefix sums because only the current prefix value is needed.
Test Cases
import sys
import io
def solve(inp: str) -> str:
old_stdin = sys.stdin
sys.stdin = io.StringIO(inp)
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
total = sum(a)
prefix = 0
best = -1
ans = 1
for i in range(n - 1):
prefix += a[i]
cur = prefix * (total - prefix)
if cur > best:
best = cur
ans = i + 1
sys.stdin = old_stdin
return str(ans)
assert solve("""3
1 2 3
""") == "2", "sample 1"
assert solve("""5
10 1 1 1 10
""") == "2", "sample 2"
assert solve("""2
5 7
""") == "1", "minimum size"
assert solve("""5
4 4 4 4 4
""") == "2", "all equal values"
assert solve("""6
1 1000000000 1 1 1 1
""") == "2", "large values"
assert solve("""4
1 1 1 10
""") == "3", "boundary near end"
| Test input | Expected output | What it validates |
|---|---|---|
2 / 5 7 |
1 |
Smallest possible array |
5 / 4 4 4 4 4 |
2 |
Equal values and middle split |
6 / 1 1000000000 1 1 1 1 |
2 |
Large integer multiplication |
4 / 1 1 1 10 |
3 |
Best cut near the right boundary |
Edge Cases
For the minimum size case:
2
5 7
the algorithm performs exactly one iteration. The prefix becomes 5, the suffix becomes 7, and the product is 35. Since there is only one valid partition, the answer is correctly 1.
For repeated values:
5
4 4 4 4 4
the total sum is 20. The prefix sums considered are 4, 8, 12, and 16, giving products 64, 96, 96, and 64. The algorithm keeps the first maximum at position 2, which is a valid answer.
For very large elements:
6
1 1000000000 1 1 1 1
the product values exceed normal 32-bit integer limits. Python's integer arithmetic handles these values directly, so no special conversion is needed.
For a cut close to the end:
4
1 1 1 10
the prefix sums are 1, 2, and 3, while the suffix sums are 12, 11, and 10. The products are 12, 22, and 30, so the algorithm selects position 3. The final element is never considered as a cut position, which prevents an invalid empty suffix.