Maximum contiguous sub-array (With most number of elements)

Question

Given an array of natural numbers and an another natural T, how to find the contiguous subarray with sum less than or equal to T but the number of element in this subarray is maximized?

For example, if the given array is:

{3, 1, 2, 1, 1} and T = 5. Then the maximum contigous subarray is {1, 2, 1, 1} because it will contain 5 elements and the sum is equal to 5.

Another example: {10,1,1,1,1,3,6,7} with T = 8. Then the maximum contigous subarray is ${1,1,1,1,3}$

I can do it with O(n^2) operation. However I am looking for a linear time solution for this problem. Any ideas?

To me it seems a version of the Knapsack Problem.

Juan Lopes
– Juan Lopes

2013-03-04 18:59:50 +00:00
Commented Mar 4, 2013 at 18:59 — Juan Lopes
– Juan Lopes, Commented Mar 4, 2013 at 18:59

ams · Accepted Answer · 2013-03-04 17:46:13Z

2

It ought to be possible to do this with O(n). I've not tested this, but it looks OK:

int start = 0, end = 0;
int beststart = 0, bestend = 0;
int sum = array[0];

while (end + 1 < arraysize) {
  if (array[end + 1] + sum <= T)
    sum += array[end++];
  else
    sum -= array[start++];
  if ((end - start) > (bestend - beststart)) {
    beststart = start;
    bestend = end;
  }
}

So, basically, it moves a sliding window along the array and records the point at which end - start is the greatest.

edited Mar 4, 2013 at 17:46

answered Mar 4, 2013 at 17:12

ams

25.7k4 gold badges62 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Quixotic Over a year ago

I think you need another check ` if ((end - start) > (bestend - beststart)) { beststart = start; bestend = end; }` at the end.

ams Over a year ago

@Quixotic: is that better now?

FredericS · Accepted Answer · 2013-03-04 17:07:41Z

0

It seems to be a capped version of the Maximum subarray problem: http://en.wikipedia.org/wiki/Maximum_subarray_problem I guess you can find inspirations with existing algorithms.

answered Mar 4, 2013 at 17:07

FredericS

4134 silver badges9 bronze badges

Collectives™ on Stack Overflow

Maximum contiguous sub-array (With most number of elements)

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related