题面：
思路：
通过前缀和的思想，从0开始，当前值即为(sum+a[i])%p，用upper_bound查看map中是否有比当前值大的，如果有，那必然是比当前值少了k倍的p，那么起点则为upper出来的值，如果没有，则起点为0，比较当前（sum减去起点处的前缀和值加p）%p是否大于当前最大值，如果
展开全文
题目如上：
题解：
题目意思
给你 n 个数字和一个数 p，要找一个连续的子段，使得这个子段的和除以 p 的余数最大。
比如数组 [3,4,5,6,7]，p=10；选子段 [2,3]，和是 4+5=9，9%10=9，余数最大，输出：2 3 9
关键想法
1. 用前缀和简化
子段 [l, r]的和除以
展开全文
题目
输入
输出
思路
题目要求最大的子段和，可以先将数组求前缀和，转换为求最大的sum[r]-sum[l-1]。
同时由于要对p进行取模，所以前缀和的数据并非递增的，sum[r]-sum[l-1]就可能为负数，进而结果就要加p，保证取模结果是正数。
对r进行遍历，要使子段和最大l有两者情况。
展开全文
E题 | 智乃的最大子段和取模
解题思路：
为了 求解区间和，本题需要先求前缀和并取模。用 表示区间 的和取模 。
在固定右端点 的情况下，要想让区间和 最大， 有两种可能取值：
要么尽可能小，要么刚好比 大一点点（此时减为负数，需要加上一个p）。
先说结论：对于每个 ，只需找第一个
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
