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) ?
Auto comment: topic has been updated by gagannagpal68 (previous revision, new revision, compare).
Any Update?
It’s known as max-convolution. I believe it’s impossible to solve in $$$O(n^{2-\epsilon})$$$ for any $$$\epsilon > 0$$$