arrayMaxConsecutiveSum c#


Question [arrayMaxConsecutiveSum c#] has 4 solution 2020-08-19 02:52:49 c#

As part of learning c# I engage in codesignal challenges. So far everything is going good for me, except for the test stated in the title.

The problem is that my code is not efficient enough to run under 3 seconds when the length of an array is 10^5 and the number of consecutive elements (k) is 1000. My code runs as follows:

int arrayMaxConsecutiveSum(int[] inputArray, int k) {

    int sum = 0;
    int max = 0;

    for (int i = 0; i <= inputArray.Length-k; i++)
    {
        sum = inputArray.Skip(i).Take(k).Sum();

        if (sum > max)
            max = sum;
    }

    return max;
}

All visible tests in the website run OK, but when it comes to hidden test, in test 20, an error occured, stating that

19/20 tests passed. Execution time limit exceeded on test 20: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input.

I also tried unlocking solutions but on c# the code is somewhat similar to this but he didn't use LINQ. I also tried to run it together with the hidden tests but same error occurred, which is weird as how it was submitted as a solution when it didn't even passed all tests.

Is there any faster way to get the sum of an array?

I also thought of unlocking the hidden tests, but I think it won't give me any specific solution as the problem would still persists.


Question [arrayMaxConsecutiveSum c#] solution number 1

It would seem that you are doing the addition of k numbers for every loop. This pseudo code should be more efficient:

  • Take the sum of the first k elements and set this to be the max.

  • Loop as you had before, but each time subtract from the existing sum the element at i-1 and add the element at i + k.

  • Check for max as before and repeat.

  • None

    The difference here is about the number of additions in each loop. In the original code you add k elements for every loop, in this code, within each loop you subtract a single element and add a single element to an existing sum, so this is 2 operations versus k operations. Your code starts to slow down as k gets large for large arrays.


    Question [arrayMaxConsecutiveSum c#] solution number 2

    For this specific case, I would suggest you not to use Skip method as it iterates on the collection every time. You can check the Skip implementation at here. Copying the code for reference.

        public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count) {
            if (source == null) throw Error.ArgumentNull("source");
            return SkipIterator<TSource>(source, count);
        }
    
        static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source, int count) {
            using (IEnumerator<TSource> e = source.GetEnumerator()) {
                while (count > 0 && e.MoveNext()) count--;
                if (count <= 0) {
                    while (e.MoveNext()) yield return e.Current;
                }
            }
        }
    

    As you can see Skip iterates the collection everytime, so if you have a huge collection with k as a high number, than you can see the execution time sluggish.

    Instead of using Skip, you can write simple for loop which iterates required items:

    public static int arrayMaxConsecutiveSum(int[] inputArray, int k) 
    {
    
        int sum = 0;
        int max = 0;
    
        for (int i = 0; i <= inputArray.Length-k; i++)
        {
            sum = 0;
            for (int j = i; j < k + i; j++)
            {
                sum += inputArray[j];
            }
    
            if (sum > max)
                max = sum;
        }
        return max;
    }
    

    You can check this dotnet fiddle -- https://dotnetfiddle.net/RrUmZX where you can compare the time difference. For through benchmarking, I would suggest to look into Benchmark.Net.


    Question [arrayMaxConsecutiveSum c#] solution number 3

    You need to be careful when using LINQ and thinking about performance. Not that it's slow, but that it can easily hide a big operation behind a single word. In this line:

    sum = inputArray.Skip(i).Take(k).Sum();
    

    Skip(i) and Take(k) will both take approximately as long as a for loop, stepping through thousands of rows, and that line is run for every one of the thousands of items in the main loop.

    There's no magic command that is faster, instead you have to rethink your approach to do the minimum of steps inside the loop. In this case you could remember the sum from each step and just add or remove individual values, rather than recalculating the whole thing every time.

    public static int arrayMaxConsecutiveSum(int[] inputArray, int k) 
    {
        int sum = 0;
        int max = 0;
    
        for (int i = 0; i <= inputArray.Length-k; i++)
        {
            // Add the next item
            sum += inputArray[i];
    
            // Limit the sum to k items
            if (i > k) sum -= inputArray[i-k];
    
            // Is this the highest sum so far?
            if (sum > max)
                max = sum;
        }
        return max;
    }
    

    Question [arrayMaxConsecutiveSum c#] solution number 4

    This is my solution.

    public int ArrayMaxConsecutiveSum(int[] inputArray, int k)
    {
        int max = inputArray.Take(k).Sum();
        int sum = max;
    
        for (int i = 1; i <= inputArray.Length - k; i++)
        {
            sum = sum - inputArray[i- 1] + inputArray[i + k - 1];
    
            if (sum > max)
                max = sum;
        }
        return max;
    }
    

    .htaccess .net .net-core 2d 3d 3d-printing abp abstract-syntax-tree actions-on-google actionscript-3 active-directory activemq activemq-artemis acumatica adobe-xd aframe ag-grid agora.io air airflow ajax akka alert alexa algorithm alignment allure amadeus amazon-cloudformation amazon-cognito