2

Каким способом эту задачу можно решить быстрее всего?

Пробовал написать по разному, пока это самый быстрый вариант.

long sum =0;
    int left =0;
    int right = arr.length-1;
    int max = 0;
    int i = 1;

    while(left<right){
        sum++;
        if(i == right){   
            if(arr[left]+arr[i] > max){
            max = arr[left]+arr[i];
            }
            left++;
            right--;
            i = left;
        }
        if(arr[left]+arr[i] > max){
            max = arr[left]+arr[i];
        }
        if(arr[right] + arr[i] > max){      
            max = arr[right]+arr[i];
        }
        i++;
    }
    System.out.println(max);
    System.out.println(sum);

При размере массива в 100к, решает примерно 5с. sum в итоге = 2500кк. Я уверен что есть решение быстрее, но к сожалению не могу его найти. Подскажите пожалуйста.

5
  • 3
    Может сортировать массив по убыванию и взять сумму двух первых элементов.
    – tilin
    31 окт 2017 в 15:54
  • 10
    А почему бы не пройтись по массиву, запоминая два наибольших элемента?
    – VladD
    31 окт 2017 в 15:55
  • @tilin по моему это самый быстрый вариант, кончено если массив уже не отсортирован. Сидел придумывал велосипед, эх ... Спасибо.
    – Micahil
    31 окт 2017 в 16:09
  • 3
    @Micahil все же самый быстрый будет, наверное, у VladD
    – tilin
    31 окт 2017 в 16:13
  • @tilin, не наверное, а точно - решение VladD работает за линейное время, тогда как как вариант с сортировкой - за линейно-логарифмическое.
    – Xander
    31 окт 2017 в 17:25

2 ответа 2

2

Просто сложите два наибольших элемента в массиве:

max1, max2 = max(L[0], L[1]), min(L[0], L[1])
for x in L:
    if x > max2:
        max1, max2 = (x, max1) if x > max1 else (max1, x)

print(max1 + max2)

Пример.

0

Как всегда, стало интересно, насколько отличаются алгоритмы по времени работы.

Написал программку (на С++) с тремя алгоритмами - линейный, авторский :) и полный перебор.

Результат:

Линейный алгоритм:       1999985078 for 46 mks
Алгоритм автора вопроса: 1999997406 for 4324499 mks
Полный перебор:          1999985078 for 5021863 mks

Понятно, что время абсолютно точно не меряется, но в 100000 раз - это как раз и отличает для 100000 элементов O(N) от O(N2) :)

Итого, алгоритм автора не только работает практически как полный перебор, но еще и подвирает... :( Где именно - искать не стал.

#define  NOMINMAX
#include <vector>
#include <iostream>
#include <iomanip>
#include <random>
#include <limits>
#include <mutimer.hpp>

using namespace std;

constexpr int length = 100000;
constexpr int maxValue = 1000000000;
vector<int> arr;



int Micahil(const vector<int>& arr)
{
    int left =0;
    int right = arr.size() - 1;
    int max = 0;
    int i = 1;

    while(left<right){
        if(i == right){
            if(arr[left]+arr[i] > max){
                max = arr[left]+arr[i];
            }
            left++;
            right--;
            i = left;
        }
        if(arr[left]+arr[i] > max){
            max = arr[left]+arr[i];
        }
        if(arr[right] + arr[i] > max){
            max = arr[right]+arr[i];
        }
        i++;
    }
    return max;
}

int Harry(const vector<int>& arr)
{
    int max0 = arr[0], max1 = arr[1];
    if (max0 < max1) swap(max0, max1);
    for(size_t i = 2; i < length; ++i)
    {
        if (arr[i] > max1)
        {
            max1 = arr[i];
            if (max0 < max1) swap(max0, max1);
        }
    }
    return max0 + max1;
}

int Exhaust(const vector<int>& arr)
{
    int max = std::numeric_limits<int>::min();
    for(int i = 0; i < length; ++i)
    {
        for(int j = i+1; j < length; ++j)
        {
            int sum = arr[i] + arr[j];
            if (sum > max) max = sum;
        }
    }
    return max;
}


int main(int argc, const char * argv[])
{
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, maxValue);
    arr.reserve(length);
    for(size_t i = 0; i < length; ++i)
        arr.push_back(dis(gen));

    {
        muTimer mu;
        int res = Harry(arr);
        mu.stop();
        cout << res << " for " << mu.duration() << "mks\n";
    }
    {
        muTimer mu;
        int res = Micahil(arr);
        mu.stop();
        cout << res << " for " << mu.duration() << "mks\n";
    }
    {
        muTimer mu;
        int res = Exhaust(arr);
        mu.stop();
        cout << res << " for " << mu.duration() << "mks\n";
    }

}

(muTimer - мой измеритель времени :))

1
  • да, иногда врет. Тоже искать не стал так как все оказалось намного проще.
    – Micahil
    31 окт 2017 в 18:05

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.