Help-Improving runtime complexity of the method

[moshiko]

Hello everyone,
Looking for a more efficient solution to method 'what', in terms of run-time complexity and space.
The method finds the largest cell sequence that the organs sum is divided by 3.(Correct me if I'm wrong)
As it seems runtime complexity here is O(n ^ 3).
I came to solution of O(n ^ 2), is there a more effective solution? Explain please,
Thanks for the helpers !

 

[jedishrfu]

It seems you are resumming things over and over in the f method

f(a,0,3) means sum elements a[0..3]

then you do f(a,0,4) which means sum elements a[0..4]

why not remember the sum and just add a[4] to it?

This will eliminate the innermost loop in the f method.

 

[jim mcnamara]

As a good rule of thumb, correct algorithms have the potential to contribute the most to efficiency.

If I understand what this code is supposed to do, I would consider a different algorithm - Kadane's maximum subarray algorithm.
https://en.wikipedia.org/wiki/Maximum_subarray_problem

 

[jim mcnamara]

Hmm - found this in my code store, made simple example in C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Kadanes Algorithm  in C
// Parameters:
// a array of integers
// sz number of elements in the array

int max_sum_subarr(int *a, const size_t sz)
{
    int i=0;
    int local_mx = INT_MIN;
    int mx_ending = 0;
    for (i = 0; i < sz; i++)
    {
        mx_ending = mx_ending + a[i];
        if (local_mx < mx_ending)
            local_mx = mx_ending;
        if (mx_ending < 0)
            mx_ending = 0;
    }
    return local_mx;
}
int main(int argc, char **argv)
{
   size_t sz=7;
   int a[7]={1 , 4, -1, -7, 3, 2, 1 };
   
   printf("maximum sub array = %d\n", max_sum_subarr(a, sz) );
   
   return 0;
}

Note the complexity change.

 

[moshiko]

I need to find algorithm to method that return the size of largest sequence that his amounts divisible by 3, in O N complexity..
for example, for array {0,0,1,1,1,1,1} the method return 5 . {0,0,1,1,1}