Optimization of obvious task-CodePudding

My task is very simple, but the most obvious solution is too slow.

I have a massive of positive elements and some questions connected with this massive. I have to find the longest segment (l,r) (with given l) with the sum of the elements less than given S. My code should be in the C language, I have tried to find that (l,r) segment with trivial for or while (just starting cycle for l element and going farther while sum is less then S, but it's too slow). My teacher recommended me to count all sums from 0 to i and use this sums to find needed segment (l,r), but I really have no idea how to make it. Example of test:

First number N (10) is the number of elements in massive
Second number K (7) is the number of tests
Next 10 numbers (1,4,0,5,6,0,0,1,5,3) are elements of array
Last 7 pairs of elements are tests (first number is l and second is sum)
And the anwsers are

My code

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

uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n);


int main() {;
    FILE *f = fopen("input.txt","r");
    FILE *s = fopen("output.txt","w");
    uint32_t n,t,l;
    uint64_t sum;
    fscanf(f,"%d",&n);
    fscanf(f,"%d",&t);
    uint32_t *arr = malloc(sizeof (uint32_t) * n);
    for( int i = 0; i < n; i  ){
        fscanf(f,"%d",&arr[i]);
    }
    for( int i = 0; i < t; i  ){
        fscanf(f,"%d %lld",&l,&sum);
        Query(l,sum,arr,n);
    }
    return 0;
}

uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n){
    uint64_t summy = 0;
    uint32_t  i;
    for( i = l ; i < n; i  ){
        summy = arr[i];
        if (summy > sum){
            return i;
        }
    }
    return i;
}

CodePudding user response：

For speed; if you know the sum of the segment (l, r), then you can determine the sum of the segment (l 1, r 1) by subtracting the entry at array[l] and adding the entry at array[r 1].

Therefore (untested):

void FindHighestSum (const uint32_t *array, uint32_t arraySize, uint32_t segmentSize) {
    uint32_t bestSumPos;
    uint64_t bestSum;
    uint32_t r;
    uint32_t l;
    uint64_t sum = 0;

    if(arraySize < segmentSize) {
        printf("Error: Array too small for segment size\n");
        return;
    }

    // Find sum of first segment

    for(r = 0; r < segmentSize; r  ) {
        sum  = array[r];
    }

    // Sum of first segment is the largest sum so far

    bestSumPos = 0;
    bestSum = sum;

    // Find largest sum of all segments

    for(l = 1; l < arraySize - segmentSize; l  ) {
        sum = sum - array[l]   array[r];
        r  ;

        if(sum > bestSum) {
            // Found a new largest sum
            bestSumPos = l;
            bestSum = sum;
        }
    }
    printf("Highest sum from %" PRIu32 " to %" PRIu32 " (sum is %" PRIu64 ")\n", bestSumPos, bestSumPos   segmentSize - 1, bestSum);
}

CodePudding user response：

I think what your teacher meant, was, instead of storing x[i] = a[i]:

for( int i = 0; i < n; i  ){
    fscanf(f,"%d",&arr[i]);
}

you could the running sum x[i] = \sum_{n=0}^{i} x[n], this is the analog of storing the integral:

int energy = 0;
for( int i = 0; i < n; i  ) {
    int value;
    if(fscanf(f,"%d",&value) != 1) exit(EXIT_FAILURE);
    energy  = value;
    arr[i] = energy;
}

Because the problem is linear, this allows you to look at only the endpoints. Thus, you can reduce your search incrementing at every step, O(n), and use a binary search, O(log n). Specifically, you will need to take the upper bound; there is no standard way of doing this in C, so you will have to write your own from bsearch and upper bound.