Минимаксная задача ранга Хакера, максимальная сумма, дающая неправильные отрицательные значения - PullRequest
Новая
       15

Минимаксная задача ранга Хакера, максимальная сумма, дающая неправильные отрицательные значения

1 голос
/ 20 июня 2019

Я сейчас решаю эту проблему на Hackerrank: https://www.hackerrank.com/challenges/mini-max-sum/problem

Я прошел только 5 из 15 тестовых случаев. Проблема в выводе максимальной суммы.

В коде сначала я нахожу максимальный и минимальный элемент в векторе, обозначаемый как max и min. minI и maxI - индексы минимального и максимального значения.

При вычислении максимальной суммы я кладу arr [minI] = 0 (поэтому вектор сводится к элементам, которые дают максимальную сумму). Как только максимальная сумма получена, я положил arr [minI] = min, следовательно, восстановив исходный вектор Затем я повторяю процесс, помещая arr [maxI] = 0; таким образом получается как минимальная, так и максимальная сумма n-1 элементов. Я знаю, что это трудно понять, но кто-нибудь может помочь мне разобраться в проблеме здесь.

Я пытался использовать arr.erase () и arr.insert (), но у меня возникли проблемы с индексацией. 

void miniMaxSum(vector<int> arr) {
int max = arr[0];
int min = arr[0];
int minI = 0;
int maxI = 0;
  for (int i = 0; i < arr.size(); i++) {
    if(arr[i] > max){
        max = arr[i];
        maxI = i;
    }
    if(arr[i] < min){
        min = arr[i];
        minI = i;
    }
  }


  arr[minI] = 0;
  int maxsum = 0;
  for(int i = 0; i<arr.size(); i++){
      maxsum += arr[i];
  }

  arr[minI] = min;


  arr[maxI] = 0;
  int minsum = 0;
  for(int i = 0; i<arr.size(); i++){
      minsum += arr[i];
  }


  cout << minsum << " " << maxsum;
}

Например, ввод одного контрольного примера был:

140537896 243908675 670291834 923018467 520718469

Правильный ответ на приведенный выше ввод: 1575456874 2357937445

Мой ответ для приведенного выше ввода: 1575456874 -1937029851

Ответы [ 2 ]

0 голосов
/ 20 июня 2019

Отрицательные суммы после добавления положительных целых чисел почти всегда указывают на проблему: вы получаете переполнение.

Эта проблема имеет ограничение: 

1 <= arr[i] <= 10^9

Когда вы добавляете четыре близких числадо 10 ^ 9 вы переполняете 32-битное целое число.Следовательно, вам нужно переключиться на больший тип данных - uint64_t будет хорошим кандидатом.

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

0 голосов
/ 20 июня 2019

Очевидно, на этой платформе int имеет 32-битную длину, что означает, что он имеет диапазон от -2147483647 до 2137483647.Превышение максимального значения является неопределенным поведением.

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

...