0

Given an array of natural numbers, find the sum of the largest contiguous subarray of a given size k. Example: 

int array = {3, 6, 90, 23, 7, 1, 8, 3};
int k = 3;

The sum should be 120 (90+23+7).

Example code: 

#include <stdio.h>
int main(void) {
    int arraysize = 9;
    int array[9] = {3, 6, 9, 20, 40, 60, 1, 2, 3};
    int k = 3;
    int max = 0;
    int maxcurrent = 0;
    for (int i = 0; i < (arraysize - k); i++) {
        for (int j = 0; j < k; j++) {
            maxcurrent += array[i + j]; 
        }
        if (maxcurrent > max) { max = maxcurrent; }
        maxcurrent = 0;
    }
    printf("%d\n", max);
}
Mitsos101
  • 551
  • 3
  • 15
  • 2
    That's an interesting problem; how did you try to solve it? – Scott Hunter Mar 02 '16 at 20:03
  • You can just try each subarray. – Bill the Lizard Mar 02 '16 at 20:04
  • 1
    It would be more interesting without a given k, and with allowing negative numbers. – wvdz Mar 02 '16 at 20:05
  • @templatetypedef This is not a duplicate, the other question is about a subarray of _at least_ length L, not *exactly* length L. – Mitsos101 Mar 02 '16 at 20:17
  • 2
    @Mitsos101: Which just makes it easier. Anyway, it is **your** homework, so you are supposed to provide at least some reasonable code. – too honest for this site Mar 02 '16 at 20:40
  • @Olaf It's not homework. Also, I came up with a solution on my own, but I wanted to see if I could optimize it somehow. – Mitsos101 Mar 02 '16 at 20:55
  • @Mitsos101 I believe the linked question also asks about subarrays of length at least L rather than exactly L. Am I mistaken? – templatetypedef Mar 02 '16 at 21:13
  • @Mitsos101 Yes, you can optimize - there is no need to sum all numbers in range again at every step. Just make a little modification of sum. – MBo Mar 03 '16 at 08:46
  • @templatetypedef This question asks about subarrays of exactly length L. – Mitsos101 Mar 03 '16 at 10:10
  • @MBo How can I do that? – Mitsos101 Mar 03 '16 at 10:10
  • 1
    @Mitsos101 Array `(a b c d e f g)`, k=4. The first sum is `S1=a+b+c+d`. The second sum is `S2=b+c+d+e`. How to make S2 from the last sum S1? Think about this. – MBo Mar 03 '16 at 10:38
  • The trick you're looking for is called "sliding window". Take that as a hint, or google it. To speed this up even more than that, there might be a SIMD-vector way to do it. If you computed prefix-sums of the whole array, you could quickly answer queries for different `k`. SIMD packed operations (including packed max) can be used to check multiple windows in parallel. SIMD prefix-sums are possible, but not easy. Google will give good results for any of these terms. – Peter Cordes Mar 04 '16 at 06:26

0 Answers0