vendredi 25 septembre 2015

Max Sum Of Integers

Here is the challenge description: http://ift.tt/1Mv1JoI
I keep getting a partially solved score. I want to know why. As in my eyes, this code works. And I believe that it is O(N) time. Thanks for looking!

Here is my code:

    #include <iostream>
    #include <fstream>
    #include <cstdlib>
    #include <vector>
    #include <string>
    #include <sstream>

    using namespace std;

    int max(int a, int b)
    {
        if (a > b)
            return a;
        else return b;
    }


    int maxSubArray(vector<int> values)
    {
        int max_so_far = values[0];
        int curr_max = values[0];
        for(int i = 1; i < values.size(); ++i)
        {
            curr_max = max(values[i], curr_max + values[i]);
            max_so_far = max(max_so_far, curr_max);
        }
        return max_so_far;
    }

    int main(int argc, char *argv[]) 
    {
        std::vector<vector<int> > Values; //to hold the values of the stock price change
        ifstream file(argv[1]);
        std::string line; //for the txt file input
        int value = 0; //for holding the value of stock change

        while (std::getline(file, line)) 
        {
            int pos = 0;
            if(line.length() == 0)
                continue;
            else
            {
                std::istringstream iss(line);
                std::vector<int> list; // temporary list of values to be pushed back into the 2-d vector
                while (iss >> value)
                {   
                    list.push_back(value);  
                }

                Values.push_back(list);
            }
        }

        for(int i = 0; i < Values.size(); ++i)
        {
            cout << maxSubArray(Values[i]);
            cout << endl;
        }
    /*  
        cout << " Printing the values : " << endl;
        for (int j = 0; j < Values.size(); ++j)
        {
            for (int k = 0; k < Values[j].size(); ++k)
                cout << Values[j][k] << " ";
            cout << endl;
        }
    */
        return 0;
    } 

Aucun commentaire:

Enregistrer un commentaire