题解 | #小美的加法#

题解（枚举）

在每个方案中，我们需要选择一组相邻元素做乘法，而剩余元素做加法。一开始用前缀和求前后两段加法的值，其实没必要，只需要从整体和 sum 中减去做乘法的两个元素就好了。

fun main(args: Array<String>) {
    val n = nextInt()
    val nums = nextArrayI(n)
    val sum = nums.fold(0L) { it, arr -> it + arr }
    var ret = sum
    for (i in 1 until n) {
        ret = max(ret, sum - nums[i] - nums[i - 1] + 1L * nums[i] * nums[i - 1])
    }
    println(ret)
    done()
}

复杂度分析：

时间复杂度： $O(n)$ 预处理整体和和枚举的时间都是 $O(n)$ ；
空间复杂度： $O(n)$ nums 数组空间。