给定一个连续的数字序列S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767).我们定义一个函数和sum(i, j) = Si + ... + Sj (1 ≤ i ≤ j ≤ n).
现在给一个整数m (m > 0), 你的任务是找到m对i和j的和sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) 最大的 (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx 是不许的）
但我很懒,我不想写special-judge模块,所以你不必输出m对i和j,只是输出最大的总和的数目sum(ix, jx)(1 ≤ x ≤ m) 代替。
总的来说就是经典动态规划，求最大M子段。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024