Can anyone help me to solve MAXSPSUM?
Hi,
I haven’t implemented this idea but I guess it should work.
Note that all the numbers are from 1 to 10^5 so you can find prime factors beforehand using a sieve for all those numbers.
Now you can use two pointers approach.
Maintain a set which stores all the distinct prime factors for a window.
Notice that the maximum size of the allowed set is K/S
because after that the contribution will be negative. so maintain this constraint in the two-pointer approach.
Maintain the max sum using the prefix array for a valid window and update it for maximum sum.
Hope it helps.