Geek Answers Handbook

Maximum continuous sub-array (with lots of elements)

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

For example, if the given array:

{3, 1, 2, 1, 1} and T = 5 . Then the maximum continual subframe is {1, 2, 1, 1} , because it will contain 5 elements, and the sum is 5.

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

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

+4
source share
2 answers

This should be possible with O (n). I have not tested this, but it looks fine:

 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 the sliding window along the array and records the point at which end - start is the largest.

+2
source

This seems to be a limited version of the problem with max Subaru: http://en.wikipedia.org/wiki/Maximum_subarray_problem I think you can find inspiration in existing algorithms.

0
source

More articles:


All Articles