Help In MAXSPSUM

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.