Can we solve this problem the hard way?

Revision en4, by gagannagpal68, 2019-08-02 05:28:24

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) ?

Tags #dp, standard algorithms, observation, education round 69, #math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English gagannagpal68 2019-08-02 05:28:24 5 Tiny change: 'nExample\n\nn = 3\n' -> 'nExample\nn = 3\n'
en3 English gagannagpal68 2019-08-02 05:27:14 2 Tiny change: '\nn = 3\ngiven ar' -> '\nn = 3\n\ngiven ar'
en2 English gagannagpal68 2019-08-02 05:26:58 8
en1 English gagannagpal68 2019-08-02 05:26:01 541 Initial revision (published)