Решение Maxium попарного продукта с использованием метода сортировки - PullRequest
Новая
       18

Решение Maxium попарного продукта с использованием метода сортировки

0 голосов
/ 02 мая 2019

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

Отлично работает для меньших цифр, но не для 10 ^ 5 цифр.

Может кто-нибудь, пожалуйста, посмотрите это и помогите?

это моя функция 

long long MaxPairwiseProductFast(const vector<int> &number)
{
    long long result = 0;
    long n = number.size();
    result = number.at(n-1) * number.at(n-2);
    return result;
}

и это моя основная функция 

int main()
{
    int n;
    cin>>n;
    vector<int>numbers(n);
    for(int i = 0; i <n; i++){
     cin>>numbers[i];
    }
   sort(numbers.begin(), numbers.end());

    long long result = MaxPairwiseProductFast(numbers);

    cout<<result<<"\n";

    return 0;
}

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

Ответы [ 2 ]

1 голос
/ 02 мая 2019

Вам не нужно менять все типы данных, как предлагают другие ответы. Просто исправьте свое умножение так: 

long long MaxPairwiseProductFast(const vector<int> &number)
{
    long long result = 0;
    long n = number.size();
    result = number.at(n-1) * (long long)number.at(n-2);
    return result;
}

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

Также проверьте произведение наименьшего двух чисел, как предлагает Бишал, поскольку -5 * -5> 4 * 4

1 голос
/ 02 мая 2019

Прежде всего вам нужно изменить тип данных вектора с int на long long везде, где вы написали vector<int>number на vector<long long>number.

Еще одно изменение, которое необходимо сделать, чтобы получить правильный вывод, - подумать о случае, когда есть как минимум два больших отрицательных числа.

Например: если вектор содержит: {-10, -5, -2, 0, 1, 2}.
Ваша программа выведет: 1 * 2 = 2 в качестве ответа.
Но ответ для этого случая будет: -10 * -5 = 50.

Итак, исправленный метод расчета будет: 

long long MaxPairwiseProductFast(const vector<long long> &number)
{
  long long result = 0;
  long n = number.size();
  if (n < 2) return 0;
  result = number.at(n-1) * number.at(n-2);
  result = max(result, number.at(0) * number.at(1));
  return result;
}
...