最大‎连‎续和再‎续

来源:m-dot.com   作者:   发表时间:2020-02-15 17:51:02

在求最大连续和的基础上,求得连续序列的始末位置

要求:The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

25 6 -1 5 4 -77 0 6 -1 1 -6 7 -5

Case 1:14 1 4Case 2:7 1 6

状态转移方程又两种选择,第一种二维dp(好不容易自己想了一个还让时间卡掉了):dp[k][j]=max(dp[k][j-1] a[j],a[j]);我们已dp[k][j]表示从k出发到j时的最优解,理论上可行,但是时间只给了1s,这种O(t*n^2)的思路被卡掉也很正常

编辑:

未经授权许可,不得转载或镜像
© Copyright © 1997-2019 by m-dot.com all rights reserved