Максимальная сумма целых чисел

Question

EDIT: решена! Я рассматривал отрицательный номер теста как 0, вместо того, чтобы выход был отрицательным. Спасибо за помощь!

Описание проблемы: https://www.codeeval.com/open_challenges/17/
Я продолжаю получать частично решенный счет. Я хочу знать, почему. Как и в моих глазах, этот код работает. И я считаю, что это O (N) время. Спасибо, что посмотрели!

Вот мой код:

#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; 
    } 

Answer 1

1. Почему вы пропускание вектора по значению здесь?

   int maxSubArray(vector<int> values)

   Это выглядит как значительные возможности оптимизации.

2. Я думаю, что вы не читаете проблему в точности. Когда они говорят «все смежные субары», они означают, что вы должны взять максимум за все i и j от for(idx = i; i < j; ++i) { total += vec[idx]; }. Сейчас ваш код в основном предполагает i = 0, который не является тем, что вы должны делать.

   Просто взглянув на выходные примеры, которые они предоставляют, я вижу, что ваш код не даст ответ, который они ожидают.

Answer 2

кажется правильным, единственное, что я могу придумать, это то, что когда список будет длинным, ваш результат может переполняться, поэтому смените int на длинный.

Answer 3

Помимо технических оптимизаций, предложенных в других ответах, касающихся алгоритма, я думаю, что небольшое исправление может заставить ваш алгоритм работать. Когда curr_max падает до отрицательного значения, из-за столкновения с отрицательным целым числом, превышающим curr_max, вы можете просто удалить все предыдущие целые числа, включая текущее значение, и начать заново. Это исправление прост, вы можете добавить одну строку в свой цикл следующим образом:

for(int i = 1; i < values.size(); ++i) 
{ 
    curr_max = max(values[i], curr_max + values[i]); 
    curr_max = max(curr_max, 0); // <---------------- add this line 
    max_so_far = max(max_so_far, curr_max); 
} 

Answer 4

поэтому я заменил код сейчас. Я получаю лучший результат, но я все равно частично.

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

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]; 
    if (curr_max < 0) 
    { 
     curr_max = 0;   
     max_so_far = 0; 
    } 
    for(int i = 1; i < values.size(); ++i) 
    { 
     curr_max = max(values[i], curr_max + values[i]); 
     curr_max = max(curr_max, 0); 
     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 
    std::string token; //for the subtring that will be converted from char to int 
    int value = 0; //for holding the value of stock change 
    int count = 0;// for holding how many total cases 

    while (!file.eof()) 
    { 
     int pos = 0; 
     getline(file, line); 
     if(line.length() == 0) 
      continue; 
     else 
     { 

      std::vector<int> list; // temporary list of values to be pushed back into the 2-d vector 

      while ((pos = line.find(",")) != std::string::npos) 
      { 
       token = line.substr(0,pos); 
       value = atoi(token.c_str()); 
       line.erase(0, pos + 1); 
       list.push_back(value); 
      } 
      value = atoi(line.c_str()); 
      list.push_back(value); 

      Values.push_back(list); 

      ++count; 
     } 
    } 

    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; 
}