好的，这是该题的题解和算法标签。

题目翻译

给定一个长度为 $n$ 的自然数数组，将其划分为两个非空连续子数组，使得两个子数组的和的乘积最大。输出划分位置 $i$（即第一个子数组的最后一个元素下标）。

题解

算法思路

设数组总和为 $S$，前缀和 $pre[i] = a_1 + a_2 + \dots + a_i$，则切分在位置 $i$ 时：

• 左部分和 = $pre[i]$
• 右部分和 = $S - pre[i]$
• 乘积 $P(i) = pre[i] \times (S - pre[i])$

展开： [ P(i) = S \cdot pre[i] - pre[i]^2 ] 这是关于 $pre[i]$ 的二次函数，开口向下，对称轴在 $pre[i] = S/2$。

因此，当 $pre[i]$ 最接近 $S/2$ 时，乘积最大。

我们只需遍历 $i = 1 \dots n-1$，找到使 $|pre[i] - S/2|$ 最小的 $i$ 即可。

时间复杂度

• 计算前缀和：$O(n)$
• 遍历寻找最优位置：$O(n)$ 总复杂度 $O(n)$，可处理 $n \le 2\times 10^5$。

空间复杂度

• 只需维护前缀和与总和，$O(1)$ 额外空间（不存整个前缀和数组也可）。

示例

输入：

3
1 2 3

总和 $S = 6$，$S/2 = 3$。

• $i=1$：$pre[1] = 1$，差 $|1-3|=2$
• $i=2$：$pre[2] = 3$，差 $|3-3|=0$

选 $i=2$，输出 2。

算法标签

• 前缀和
• 数学优化
• 贪心
• 数组

核心结论

最大乘积出现在前缀和最接近总和一半的位置。