NeverSayNever's blog

Maximum Sum Subarrays
By NeverSayNever, history, 9 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by NeverSayNever (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by NeverSayNever (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by NeverSayNever (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Refer to this: 
Maximum Sum Subarray for each K

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for the help but it seems like that this problem cannot be solve in less complexity than O(N^2).

    → Reply