I was solving this problem(https://codeforces.net/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) ?