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.