CODEWITHSUNDEEP
arraysperformanceruntime
mrig
mrig

Reputation: 402

Optimum solution for Contiguous sum of array elements

Can someone suggest the optimum solution for the following problem. Given an array of positive/negative integers, return the maximum "special sum". Given an array A, "Special sum" at each array index is defined as follows.

S[i] = S[i] + (S[i+1] + S[i+2]) + (S[i+3] + S[i+4] + S[i+5]) + (S[i+6] + S[i+7] + S[i+8] + S[i+9]) + .....

i.e. To an element at index i we add next 2 element, then next 3, then next 4 till we have those subsets of numbers available in the array.

eg; Array A[1 3 1 2 5 -5] => Result : 8 Explanation:

S[0] = 1+(3+1)+(2+5-5)=7;
s[1] = 3+(1+2)=6;
S[3] = 1+(2+5)=8; 
S[4] = 2+(5-5)=2; 
S[5] = 5; S[6] = -5;

As S[3] is max that's the result. This could be solved using 3loops, is there an optimum way to solve it?

Upvotes: 1

Views: 87

Answers (1)

dfens
dfens

Reputation: 5515

part 1

Given array S of length N consider following sequence:

R[i] = S[i+1] + s[i+2] + s[i+3] + ... + s[N-1] + s[N]
       R[i+1] = S[i+2] + s[i+3] + ... + s[N-1] + S[N]

                   ...
                                        R[N-1] = S[n]

That means that R[k] = S[k] + R[k+1]

Loop nr 1:

from N to 0 do:
  R[k] = s[k]
  if R[k+1] exists do
    R[k] = R[k] + R[k+1]

For example if N=9 sum is reflected by x'es on diagram below:

     123456789
S[0] xxxxxxxxx   
S[1]  xxxxxxxx   
S[2]   xxxxxxx   
S[3]    xxxxxx      
S[4]     xxxxx      
S[5]      xxxx      
S[6]       xxx        
S[7]        xx        
S[8]         x

part 2

We are assuming that number of elements summed per row must be triangular number (element of sequence 1+2+3..., valid elements are 1,3,6,10,...)

To visualise this let's take our example:

     123456789
S[0] xxxxxx   
S[1]  xxxxxx   
S[2]   xxxxxx   
S[3]    xxxxxx      
S[4]     xxx      
S[5]      xxx      
S[6]       xxx        
S[7]        x        
S[8]         x

Notice that in each row (with index i) there may be gaps in the end. Gaps occur when number N-i is not triangular.

For example at index i=0: N-i = 9, the biggest triangular number lower than 9 is 6

To get the lowest triangular number that fits a number use FLOOR following formula:

enter image description here

function closest_triangle(n)
  ((sqrt(8*n+1) -1) / 2).floor
end

part 2 Now simply iterate through each R[i] where i=0...N and substract unwanted parts:

for i in 0..N
  for j in 0..closest_triangle(N-i)
    R[i] = R[i] - S[i + j + 1]
  end
end

Of course you can store partial substraction sums since those will be repeated. For example if N=21:

xxxxxxxxxxxxxxxxxxxxx      
 xxxxxxxxxxxxxxx      
  xxxxxxxxxxxxxxx      
   xxxxxxxxxxxxxxx      
    xxxxxxxxxxxxxxx      
     xxxxxxxxxxxxxxx      
      xxxxxxxxxxxxxxx           
       xxxxxxxxxx           
        xxxxxxxxxx           
         xxxxxxxxxx           
          xxxxxxxxxx           
           xxxxxxxxxx               
            xxxxxx               
             xxxxxx               
              xxxxxx               
               xxxxxx                  
                xxx                  
                 xxx                  
                  xxx                    
                   x                    
                    x

So this will simplify computation (storing sum of some of last numbers).

Now on complexity:

In part 1 we are creating array of size N and we are doing N elementary operations.

In part 2 if memoization (storing of sum last N elements) will be used - then we will also have N basic operations

Thus algorithm will achieve O(n) complexity

Upvotes: 1

Related Questions