Given an unsorted array A and a number k, find the maximum sum sub string in the array such that its sum is divisible by k.
eg. k=3 arr[1,2,3,-3,-4,1,0,-2,5,4,5]
ans=12 sum from [-2,5,4,5]
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 163 |
2 | cry | 161 |
3 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | awoo | 158 |
6 | atcoder_official | 157 |
7 | adamant | 155 |
7 | nor | 155 |
9 | maroonrk | 152 |
10 | Dominater069 | 148 |
Given an unsorted array A and a number k, find the maximum sum sub string in the array such that its sum is divisible by k.
eg. k=3 arr[1,2,3,-3,-4,1,0,-2,5,4,5]
ans=12 sum from [-2,5,4,5]
Название |
---|
Uhm... What about restrictions? What is the maximum size of A, what is the maximum value of k? Maybe you have a link?
maximum size of array 10**3 k<10**2..I got this problem in the interview
Well. If array size is not greater than 1e3 and the time restriction is >1 second(like in the most CF problems), than you can just go for a brute solution:
Assymptotics:O(n * (n + 1) / 2)
P.S. You can also use prefix solution.
you can actually get O(n*k) if you use dp and store the maximum sub segment modulo k.
can you tell your approach?
just gonna write the main dp part
PS: u only actually need 2*k memory, though I am lazy.
You can actually get O(n) if you store minimum subsegment modulo k.
We want (sum[r] — sum[l — 1]) % k == 0. That also means that sum[r] % k == sum[l — 1] % k. You just need to remember the minimum sum[x < r] such that it has the same remainder when you divide by k to get the maximum answer. So just pass through the array and see if you have a new answer + update the position sum[x] % k if you need to.
Edit: this is the O(nlogn) code that works for any k (considering things don't overflow)
you are right! The constraints on k made me look for complexity in terms of k..
though I think I see 2 errors:
1)it should be max right(for the ans part)? since he is looking for the maximum sum.
2) you should print ans instead of sum?
Yes you are right my mistake ^^