首页 > 试题广场 >

小A与最大子段和

[编程题]小A与最大子段和
小A在网上看到了 "最大子段和" 问题的解法.第二天,小A向小B讲解了这个问题.
但小B抛出了一个疑问：如果让每个数的权值是它本身的值乘上它在子段中的位置呢?
小A被难住了,你能帮他解决这个问题吗?
形式化地说,你需要在一个序列 a  里找到一个非空子段(子段是连续的) b, 满足  最大( m 是 b 的长度)

输入描述:
第一行一个整数 n ,表示序列的长度
第二行 n 个整数,第 i 个数表示 a_i


输出描述:
一行一个整数，表示最大的  
示例1

输入

4
-100 1 2 3

输出

14

说明

1\times1+2\times2+3\times3=14

备注:

算法知识视频讲解
开通博客
头像 耕云种月
发表于 2022-01-25 20:59:32
原题解链接：https://ac.nowcoder.com/discuss/154293 令Ax=∑i=1xai×i,Bx=∑i=1xaiA_{x}=\sum_{i=1}^{x} a_{i} \times i, B_{x}=\sum_{i=1}^{x} a_{i}Ax​=∑i=1x​ai​×i,Bx 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

筛法(线性筛/杜教筛/洲阁筛/min_25筛)
难度：
0条回答 5浏览

热门推荐

相关试题

小A与最大子段和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号