Maximum Sum Subarrays

Revision en2, by NeverSayNever, 2015-11-17 20:38:08

Hello everyone,

I am trying to improve the time complexity of the following simple problem.

Problem: Given an array A consisting of N positive integers. For each K where (1 <= K <= N) find the largest sum sub array of size K. You just need to output the largest sum for each size K.

Sample Input:
4
1 3 2 1

Sample Output:
3 5 6 7

Any solution or idea better than O(N^2) is welcome. Any help will be appreciated.

Tags data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English NeverSayNever 2015-11-17 20:39:46 29
en3 English NeverSayNever 2015-11-17 20:38:33 9 Tiny change: ' an array <b>A</b> consistin' -> ' an array $A$ consistin'
en2 English NeverSayNever 2015-11-17 20:38:08 61
en1 English NeverSayNever 2015-11-17 20:35:53 454 Initial revision (published)