I was solving this problem(https://codeforces.com/contest/1197/problem/D) from a recent contest. Eventually, I came up with Dp. But in the process of solving, I proved if I can answer below problem then I can easily use that to solve the original problem.
Problem: Given an array of integers, We need to print an array sz of length n. sz[i] should print the value of maximum sum of i-length subarray.
Example n = 3 given array: 4 -2 5
ans: 5 3 7
Can we solve the problem in O(nlogn) ?