Strange output from simple C program to find the largest continuous subarray in an array

Question

I am very new to C, and I was just playing around and seeing if I could recreate a simple subarray adding program (finds the largest continuous subarray in an array). I ran in to an odd issue where if I defined n as an integer and used it as a condition in my for loop I would get absolute junk back.

Forgive this weird code, I pretty much just copied and pasted a file I was monkeying around with (lots of extra printfs etc). If I run this, I get an output of "4196053", or something similar to that, for each printf call in the for loop. Even in the first printf call (before entering the loop) it seems to be messed up.

#include <stdio.h>

int maxI (int a, int b)
{
        int max = (a >= b) ? a : b;
        return max;
}


int main (void)
{
    int array[] = { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5};
    int n = 11;
    int maxSoFar, i = 0;
    int maxHere = 0;
    printf ("%i\n", maxSoFar); //why is it screwing up here?

    for (i = 0; i < n; i++) {
            printf ("%i\n", maxSoFar);
            maxHere = maxI(maxHere + array[i], 0);
            maxSoFar = maxI(maxSoFar, maxHere);
    }
    printf ("The max is %i.\n", maxSoFar);
    return 0;
}

If I just use 11 in the conditional instead of a variable it works fine. Anyone know what is going on here?

It's "screwing up" the first `printf` because you initialized `i`, but not `maxSoFar` in the declaration. 'int maxSoFar, i = 0;` only initializes `i`. — Ken White, Sep 05 '13 at 02:23
I suppose I made it pretty obvious (with my code) how new to C I am. Anyone know why it seems to work when I don't initialize n and just use 11 in the for loop? — Jeremy Watson, Sep 05 '13 at 02:28
An uninitialized variable contains whatever random data happens to be in memory at that location when the variable is used, and the behavior is undefined. I have no idea what "just use 11 in the for loop" means, but adding anything to a random value results in another random value. — Ken White, Sep 05 '13 at 02:31
See my comment on P0W's answer for an explanation of why it worked when you were not using `n`. — Chris Hayes, Sep 05 '13 at 02:49
@KenWhite: "Arbitrary data" would be more accurate than "random data". The word "random" has a lot of mathematical implications that don't apply here. — Keith Thompson, Sep 05 '13 at 03:01
@KenWhite I am sorry I wasn't clear, I meant using 11 as the test for i. — Jeremy Watson, Sep 05 '13 at 03:18
@KeithThompson: Probably right, but "random" in the context I used it seems appropriate: Some unpredictable value that happens to be on the stack location your variable is pointing at when you access it is arbitrary, but it's probably pretty random as well (as in "there's no way to guess what it might be", in the same way the common vernacular says "some random guy off the street was asked". :-) — Ken White, Sep 05 '13 at 03:24

P0W · Accepted Answer · 2013-09-05T03:03:01.170

1

maxSoFar is having some arbitrary data, so you need to initialize it first

int maxSoFar = 0, i = 0;
     ^^Initialize to zero

edited Sep 05 '13 at 03:03

answered Sep 05 '13 at 02:23

P0W

46,614
9
72
119

Ah thanks, any idea as to why it seems to work when I do not use n as a variable? – Jeremy Watson Sep 05 '13 at 02:26
@JeremyWatson It's undefined behavior. There is no explanation for why that works because undefined behavior. – Scotty Bauer Sep 05 '13 at 02:27
@JeremyWatson there's no reason/explanation, if luckily something happens, the behavior is undefined. Ref-[this](http://stackoverflow.com/a/4105123/1870232). In this case I'd say your are _unlucky_ to get expected output. – P0W Sep 05 '13 at 02:37
@JeremyWatson: If you do not use `n` in the loop condition, your compiler is likely noticing that it is not being used and compiles it out. This reduces the size of the stack, moving `maxSoFar` into a memory region which, in your case, appears to have had a 0 in it, causing your program to work. As P0W says, this is definitely unlucky; you want to catch these errors as soon as possible. – Chris Hayes Sep 05 '13 at 02:48

score 0 · Answer 2 · answered Sep 05 '13 at 02:23

0

Your error is here

int maxSoFar, i = 0

You never declared maxSoFar so it's using garbage data.

Initialize it to 0, and you should be good.

answered Sep 05 '13 at 02:23

Scotty Bauer

1,277
9
14

score 0 · Answer 3 · answered Sep 05 '13 at 02:26

0

It gives you a garbage value because you never initialize maxSoFar. This means that it will have the value of whatever was left in memory at that point.

answered Sep 05 '13 at 02:26

Yuushi

25,132
7
63
81

score 0 · Answer 4 · answered Sep 05 '13 at 02:54

You main issue is that maxSoFar is a local(automatic) variable and is therefore if it is not initialized it will have an indeterminate value, so the results of this program are also indeterminate. The fix would be to properly initialize maxSoFar, probably to the first element of array.

For completeness sake, the relevant section of the C99 draft standard is 6.7.8 Initialization paragraph 10 which says:

If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate.[...]

Strange output from simple C program to find the largest continuous subarray in an array

4 Answers4