CODEWITHSUNDEEP
carraysalgorithm
Elnaz
Elnaz

Reputation: 1093

To Find the maximum consecutive sum of integers in an array

I have this implementation, the result of this program is 100 but the correct answer is 103. is anyone knows what is wrong in this implementation or if there is a better way for Finding the maximum consecutive sum of integers in an array?

Thanks in advance. 

#include <stdio.h>

int main(void) {
int a[] = { -3, 100, -4, -2, 9, -63, -200, 55 };
int max_sum, temp_sum, i, n = 12, t;
temp_sum = max_sum = a[0];
for (i = 1; i < n; i++) {
    if (a[i] > 0)
        temp_sum += a[i];
    else {
        t = 0;
        while (a[i] < 0 && i < n) {
            t += a[i];
            i++;
        }
        if (temp_sum + t > 0) {
            temp_sum = temp_sum + t + a[i];
            if (temp_sum > max_sum)
                max_sum = temp_sum;
        } else if (i < n)
            temp_sum = a[i];
    }
}
if (temp_sum > max_sum)
    max_sum = temp_sum;
printf("Maximum Numbers is %d \n", max_sum);
return 0;
}

Upvotes: 3

Views: 9815

Answers (4)

Skiminok
Skiminok

Reputation: 2871

I suggest Kadane's algorithm. In C++ it will be something like this (untested): 

int maxSubarray(std::vector<int> a) {
    int maxAll = 0, maxHere = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        maxHere = std::max(a[i], maxHere + a[i]);
        maxAll = std::max(maxAll, maxHere);
    }
    return maxAll;
}

Upvotes: 4

Sam DeHaan
Sam DeHaan

Reputation: 10325

Your implementation's indices were incorrect, as noted by other users. I felt it was necessary to add an answer, however, to point out that your implementation fails if all values are negative (and the closest-to-positive number is not in the first position).

A quick fix for this issue would be to add a check when assigning temp sum in the case where a[i] < 0 && temp_sum + t < 0 - at the last else block.

} else if (i < n) {
    temp_sum = a[i];
    if (temp_sum > max_sum)
       max_sum = temp_sum;
}

Upvotes: 1

TJ C.
TJ C.

Reputation: 11

If it is looking for the largest consecutive sum not starting at index 0, the easiest way would be to have two loops

int max_sum, temp_sum, i, n = 8, t;
max_sum = a[0];
for (t = 0; t < n; t++) {
    temp_sum = 0;
    for (i = t; i<n; i++) {
        temp_sum += a[i];
        if (temp_sum > max_sum)
            max_sum = temp_sum;
    }
}

Upvotes: 0

Francis P
Francis P

Reputation: 13665

You are not using the correct indexes:

see here for demo : http://codepad.org/wbXZY5zP

int max_sum, temp_sum, i, n = 8, t;
temp_sum = max_sum = a[0];
for (i = 0; i < n; i++) {
    (...)
}

Upvotes: 6

Related Questions