Can anyone help me to solve MAXSPSUM?

https://www.codechef.com/problems/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.