gagannagpal68's blog

Can we solve this problem the hard way?
By gagannagpal68, history, 5 years ago, In English

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

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gagannagpal68 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Any Update?

→ Reply
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It’s known as max-convolution. I believe it’s impossible to solve in $$$O(n^{2-\epsilon})$$$ for any $$$\epsilon > 0$$$

→ Reply