How can this problem be solved most quickly?

I tried to write in different ways, while this is the fastest option.

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

With an array size of 100k, it decides about 5s. sum as a result = 2500kk. I am sure that there is a solution faster, but unfortunately I can not find it. Tell me please.

  • 3
    It can sort the array in descending order and take the sum of the first two elements. - tilin
  • ten
    Why not go through the array, remembering the two largest elements? - VladD
  • @tilin in my opinion is the fastest option, over if the array is not already sorted. Sat was inventing a bicycle, oh ... Thank you. - Micahil
  • 3
    @Micahil, nevertheless, VladD - tilin will probably be the fastest
  • @tilin, not sure, but for sure - the VladD solution works in linear time, whereas as a sorting option, it is linear-logarithmic. - Xander

2 answers 2

Simply add the two largest elements in the array:

 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)

An example .

    As always, it was interesting how much the algorithms differ in terms of operation time.

    I wrote a program (in C ++) with three algorithms - linear, author :) and brute force.

    Result:

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

    It is clear that time is absolutely not measured, but 100,000 times - this is exactly what distinguishes for 100000 elements O (N) from O (N 2 ) :)

    So, the author’s algorithm not only works almost like a complete brute force, but also podviraet ...: (Where exactly - did not look for.

     #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 is my time meter :))

    • yes, sometimes lying. He didn’t look either, since everything turned out to be much simpler. - Micahil