小A与最大子段和

题号：NC22579
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

小A在网上看到了 "最大子段和" 问题的解法.第二天,小A向小B讲解了这个问题.

但小B抛出了一个疑问：如果让每个数的权值是它本身的值乘上它在子段中的位置呢?

小A被难住了,你能帮他解决这个问题吗?

形式化地说,你需要在一个序列 a 里找到一个非空子段(子段是连续的) b, 满足 $\sum_{i=1}^m b[i]\times i$ 最大( m 是 b 的长度)

第一行一个整数 n ,表示序列的长度
第二行 n 个整数,第 i 个数表示

一行一个整数，表示最大的

示例1

复制

4
-100 1 2 3

复制