Calculating lowest subtotal of array in C

Question

I want to search for the lowest subtotal of k values in an array z with n elements, filled by user input. This works fine with k==1 but I do not understand why my code does not work for k>1. My program outputs the wrong index and subtotal.

The function is being called from main, after filling the array with n elements of int values in a loop until it's filled, asking for the desired length of k.

Please help me understand what I'm doing wrong

#include <stdio.h>

void lowest_subtotal(int z[], int n, int k){
   int t[]={0};
   int i = 0, position = 0, tempmin;

   if(k==1){ //working 100%
       while(i<n){
           if(z[i]<tempmin){
               tempmin=z[i];
               position=i;
           }
           i++;
        }
   printf("Lowest subtotal on Index %d. (sum: %d.)", position, tempmin);
   }

   else{
       //calculate subtotals
       while(i<=n){ 
           for(int j=0; j<k; j++){
               if(z[i+j]<0){
                   t[i] -= z[j];
               }
               else{
                   t[i] += z[j];
               }
           }
           i++;
       }
    
       //search for lowest subtotal
       i = 0;
       while(i<n-k+1){
           if(t[i] < tempmin){
               tempmin = t[i];
               position=i;
           }
       i++;
       }
       //wrong result of index and sum?
       printf("Lowest subtotal on Index %d. (sum: %d.)",position-k-1,tempmin);
   }
}
    int main(){
    int n,k; //length of vector, length of subtotal
    
    printf("n: ");
    scanf("%d",&n);
    
    int z[99] = { 0 }; //initialize array
    
    
    printf("input elements:\n");
    for(int i=0; i<n; i++){
        scanf("%d",&z[i]);
    }
    
    printf("length of subtotal?: ");
    scanf("%d",&k);
    
    lowest_subtotal(z,n,k);
}

Answer 1

It will be much easier for you if you split it into separate tasks (functions.

long long subtotal(int *arr, size_t size, size_t start, size_t k)
{
    long long result = 0;

    for(size_t index = 0; index < k; index ++)
    {
        result += arr[start + index];
    }
    return result;
}

long long smallestSubtotal(int *arr, size_t size, size_t k, size_t *startpos)
{
    long long result = LLONG_MAX;
    for(size_t start = 0; start < size - k; start++)
    {
        long long sum = subtotal(arr, size, start, k);
        if(result > sum)
        {
            if(startpos) *startpos = start;
            result = sum;
        }
    }
    return result;
}

void lowest_subtotal(int z[], size_t n, size_t k)
{
    size_t index;
    long long subt;

    subt = smallestSubtotal(z, n, k, &index);

    printf("The smallest subtotal of length %zu is %lld at index %zu\n", k, subt, index);
}

int main(void)
{
    int arr[SIZE];

    srand(time(NULL));
    for(size_t index = 0; index < SIZE; index++)
    {
        arr[index] = rand();
    }

    lowest_subtotal(arr, SIZE, 15);
}

Answer 2

As I understand from the OP code, the task is to find the starting index of k consecutive numbers in an array of n numbers such that the sum of the k numbers is minimal.

The case of k=1 need not be a special case. Besides, the idea of updating the sum of a "window" of k elements is good, but there are several errors in the implementation. A working version of lowest_subtotal() could be as follows:

#include<limits.h>

int lowest_subtotal(int z[], int n, int k)
{
    if(k > n || k < 1)
    {
        return -1;  // Error, k must be in the range from 1 to n 
    }

    // Calculate sum in window at index 0
    int sum = 0;
    for(int i = 0; i < k; i++)
    {
        sum += z[i];
    }

    // Slide window and update sum
    int index = 0;
    int min_sum = sum;
    for(int i = 1; i < n - k; i++)
    {
        sum += z[i+k-1] - z[i-1];  // Add incoming value and subtract the leaving value
        if(sum < min_sum)
        {
             min_sum = sum;
             index = i;
        }
    }
    printf("Lowest subtotal at index %d (sum=%d)\n", index, min_sum);
    return index;
}