can you tell your approach?

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)

#include <iostream>
#include <map>

typedef long long ll;

int main()
{
	ll n, k, sum = 0;
	std::cin >> n >> k;
	std::map<ll, ll> pref;
	pref[0] = 0;
	ll ans = 0;
	for(int i = 1; i <= n; i++)
	{
		ll temp;
		std::cin >> temp;
		sum += temp;
		if(pref.count((sum % k + k) % k) == 1)
		{
			ans = std::max(ans, sum - pref[(sum % k + k) % k]);
			pref[(sum % k + k) % k] = std::min(pref[(sum % k + k) % k], sum);
		}
		else
		{
			pref[(sum % k + k) % k] = sum;
		}
	}
	std::cout << ans << '\n';
}