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.