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.