How to find maximum sum of n consecutive numbers in an array in o(n)?

general
1

Maximum sum of n consecutive integers in an array
ex: 12342112334213343211 and n=4

ans is 13 ( 3, 3, 4, 3)

2

Hi avidcoder,

well it is so simple first of all take sum of initial n number then add n+1(th) number and subtract first number then add n+2 (th) number and subtract second number and for each iteration store maximum number :- code goes here

for(i=0;i < n;i++)
sum=sum+a[i];

max=sum;

for(i=n;i < length of array ;i++){

sum=sum+a[i]-a[i-n];

if ( sum > max ) max=sum;

}

print(max);

i think it was so easy but i can guess why did you ask this

3

Thanx admin123,
I know this approach but Is there any other(fast) approach for this (or) is this the only way of doing this?
what if array length exceeds 10^6?

4

for this problem you have to check each number at lest once
but if complexity is less than O(n) means you could not make any decision without knowing the value of each number. there is no other way of doing it.for n numbers there is not any algorithm in world which is better than O(n) if you did not precomputed something. but if you are solving for 10^6 then O(n) works. In one second maximum you can go upto 10^8 but you may doing other part of question with high complexity.

5

thanx. is there any optimized approach(of above code) as this takes a lot of time for large values of n and array-size ?

6

i dont know what are you doing in question but there is only one thing you may or may not using. if you are storing those numbers in array and then applying this approach so i will suggest you to do both work simultaneously first input each number one by one and store in array and find sum and check if sum>max and then input next number.
if it is possible to share your original question or other strategy then let me see it :slight_smile:

7

http://stackoverflow.com/questions/31891022/maximum-sum-of-n-consecutive-elements-of-array && thanx for ur patience .

8

well it was not original question but a same question on other plate form if minimum value of n is restricted then we can use sliding window method to find max sum with less time then O(n) but first we have to iterate from 1 to n for pre-computation of window sum it will take O(n). and query take less time then O(n) but complexity will be O(n) because O(n-k) = O(n).all these method will be efficient if number of query is large but for single query there is not any method from my side :frowning: