views:

99

answers:

3

I'm running CodeBlocks on the MingW compiler in an XP virtual machine. I wrote in some simple code, accessible at cl1p , which answers the algorithm question at CodeChef (Well it only answers it partly, as I have not yet included the loop for multiple test cases.

However, my problem is, that while running it in debug mode, it gives the correct output of 5, for the input:

3
1
2 1
1 2 3

However, when I build and run it, it gives the absurd, huge output 131078, what seems like garbage to me. I do not understand how the hell this is happening, but am guessing it's something to do with the dynamic memory allocation. What's the problem here, and how can I fix it? I even ran it through the online compiler at BotSkool, and it worked fine. After adding the loop for test cases, the code even worked correctly on CodeChef!

#include <iostream>

using namespace std;

int main()
{
    // Take In number of rows
    int numofrows;
    cin >> numofrows;

    // Input Only item in first row
    int * prevrow;
    prevrow = new int[1];
    cin >> prevrow[0];

    // For every other row
    for (int currownum = 1; currownum < numofrows; currownum++)
    {
        // Declare an array for that row's max values
        int * currow;
        currow = new int[currownum+1];

        int curnum;
        cin >> curnum;

        // If its the first element, max is prevmax + current input
        currow[0] = prevrow[0] + curnum;

        // for every element
        int i = 1;
        for (; i <= currownum; i++)
        {
            cin >> curnum;

            // if its not the first element, check whether prevmax or prev-1max is greater. Add to current input
            int max = (prevrow[i] > prevrow[i-1]) ? prevrow[i] : prevrow[i-1];

            // save as currmax.
            currow[i] = max + curnum;
        }

        // save entire array in prev
        prevrow = new int[i+1];
        prevrow = currow;
    }

    // get highest element of array
    int ans = 0;
    for (int j=0; j<numofrows; j++)
    {
        if (prevrow[j] > ans)
        {
            ans = prevrow[j];
        }
    }

    cout << ans;
}
+1  A: 

For one thing, this:

    //save entire array in prev
    prevrow = new int [i+1];
    prevrow = currow;

copies the pointer, not the whole array.

Richard Pennington
are you sure? I wanted a way to copy all of currow's values into prevrow. How do I do that?
One way would be memcpy: memcpy(prevrow, currow, sizeof(int) * i);
Richard Pennington
+1  A: 

Run the code through Valgrind on a Linux machine and you'll be amazed at how many places your code is leaking memory. If you are taking the hard road of managing your memory, do it well and 'delete' all the new-allocated memory before allocating more. If, on the other hand, you prefer the easy road, use a std::vector and forget about memory management.

pau.estalella
Wow. I was completely unaware of vectors, and feel quite stupid, since it did show up in a search for C++ equivalents to the ArrayList in Java. Anyhow, thanks, this knowledge will help me greatly. Any site you recommend to learn all the other data structures in C++?Also, the Valgrind site does not provide binaries. Any place you know I can get binaries for Mac OS X? I have an incompatible older version of XCode installed on my Mac right now, and do not want to experiment with building apps right now (not so good with Unix command line)
Include http://www.cplusplus.com/reference/ and http://www.cppreference.com/wiki/start in your bookmarks for a starter :) There you can find the data structures and algorithms provided in the C++ standard library. Tutorials about them abound. Google!
pau.estalella
Valgrind is not yet provided in binary form for Mac OS X, but you have substitutes in Mac OS X. XCode provides several free tools, like Instruments and MallocDebug.
pau.estalella
+1  A: 

In your loop, you have this line

int max = (prevrow[i]>prevrow[i-1])?prevrow[i]:prevrow[i-1];

On the first iteration of the main loop, when currownum == 1, the loop containing this line will be entered, as i is initialized to 1. But on the first iteration, prevrow only has one element and this line tries to access prevrow[1]. In a debug build, the memory simply gets initialized to zero, but in a normal build, you get some garbage value that just happened to be in the memory, leading to the result you see.

Pretty much always, when you get garbage values in a normal build, but everything is fine in a debug build, you are accessing some uninitialized memory.

Also, your program is leaking memory like crazy. For instance, you don't need to assign any result of new inside the loop to prevrow because right after that you change prevrow to point to another block of allocated memory. Also, you should call delete for any memory that you are no longer using.

jk