Need help with compilation error

[denver2020]

Hi

I am trying to implement the below logic to find the largest sum of vector {5, 9, 7, 11} is sum of elements 9 and 11, which is 20.
Can anyone tell me what is wrong in my code below? Compilation gets terminated here.

#include <stdexcept>
#include <iostream>
#include <vector>

class MaxSum
{
public:
    static int findMaxSum(const std::vector<int>& numbers)
    {   int curr = numbers[0];
        int maxsum = curr;
        for(int i = 1; i<numbers.size(); i++)
        {
          if(curr > 0)
          {
            curr = curr + numbers[i];
          }
          else
          {
            curr = numbers[i];
          }
        }
        maxsum = std::max(maxsum, curr);
        return maxsum;
     }
     
     throw std::logic_error("Waiting to be implemented");
    };


#ifndef RunTests
int main()
{
   std:: vector<int> v {5, 9, 7, 11};
   std::cout << MaxSum::findMaxSum(v);
}
#endif 

[denver2020]

In findMaxSum function, I am trying to implement logic to return largest sum of any 2 elements in given vector of numbers.

[denver2020]

26 | throw std::logic_error("Waiting to be implemented");
| ^~~~~

Compilation terminates in above line

[Ganado]

In the future, tell us the actual, verbatim compiler error.

Line 26 is not in a function. Also, your indentation is a bit misleading because the closing braces on lines 24 and 27 don't match with the opening brace indentation.

[lastchance]

The line you are referring to isn't inside any function.

[denver2020]

I mean to say compilation errors at this line
throw std::logic_error("Waiting to be implemented");

[Ganado]

We know. That line is not in a function. Just remove that line.

[denver2020]

After I remove below line, my code gives output as 32. but expected is 20, given the largest sum of vector {5, 9, 7, 11} is sum of elements 9 and 11, which is 20. How can i change this logic?

[Ganado]

Now you're in the fun part! The actual meat of the logic. I don't understand how your current function is finding which two numbers produce the largest sum. Personally, I think you should just start with a fresh version. Tackle it in a different way. Keep track of two variables: One for the largest number found so far, and then another for the second largest number found so far. At the end, you simply add the two largest numbers found (assuming the size of the data >= 2).

Side note, this logic is unnecessarily restricts you:

          if(curr > 0)
          {
            curr = curr + numbers[i];
          }
          else
          {
            curr = numbers[i];
          }

You don't need this. Just do curr = curr + numbers[i]; If curr is 0, then you'd be adding 0 anyway. [But I don't see how this part helps you accomplish the goal to begin with, so I would just discard it.]

[denver2020]

I have changed the logic now as below

#include <iostream>
using namespace std;

int main() {

  int arr [4] = {5, 9, 7, 11};
  int max = 0;
  int len = sizeof(arr)/sizeof(arr[0]);
  for (int i=0; i<len-2; i++){
    for (int j=i+2; j<len; j++){
        if ((arr[i]+arr[j]) > max)
            max = arr[i]+arr[j];
    }
  }
  
  cout << max;

  return 0;
}

[ne555]

you are missing some pairs with your «int j=i+2» optimization
for example, test against {5, 7, 9, 11}

also, that's O(n^2) but could be easily done in O(n)

[denver2020]

ok. so what is the optimal solution here considering time complexity?
I am trying to implement findMaxSum method logic that returns the largest sum of any 2 elements in the given vector of positive numbers. For example,
//largest sum of vector {5, 9, 7, 11} is sum of elements 9 and 11, which is 20.

[lastchance]

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
   int arr[] = {5, 9, 7, 11};
   int BIG = arr[0], big = arr[1];   if ( big > BIG ) swap( big, BIG );
   int N = sizeof arr / sizeof arr[0];
   for ( int i = 2; i < N; i++ )              // O(N) complexity
   {
      if ( arr[i] > big )                     // Something needs changing
      {
         if ( arr[i] > BIG ) { big = BIG;  BIG = arr[i]; }       // both need changing
         else                {             big = arr[i]; }       // only the smaller needs changing
      }
   }
   cout << "Largest sum of two elements is " << big + BIG << '\n';
}

Largest sum of two elements is 20

[Ganado]

Stares motionless and dumbstruck in horror by the use of 'BIG' and 'big' as variable names

[lastchance]

Would you prefer "awesome" and "runner_up"? "Gold" and "silver"?

[Ganado]

Ha, I like gold and silver :)

[jonnin]

winner, loser, loser, loser... :)
this is the opposite of medical school (where the guy graduating with the lowest scores is called... doctor).

[George P]

denver2020 wrote:

returns the largest sum of any 2 elements in the given vector of positive numbers.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main()
{
   std::vector<int> vec { 5, 7, 4, 2, 8, 6, 1, 9, 0, 3 };

   for (const auto& itr : vec) { std::cout << itr << ' '; }
   std::cout << '\n';

   std::sort(vec.begin(), vec.end(), std::greater<int>());

   for (const auto& itr : vec) { std::cout << itr << ' '; }
   std::cout << '\n';

   auto sum { vec[0] + vec[1] };

   std::cout << "The sum: " << sum << '\n';
}

5 7 4 2 8 6 1 9 0 3
9 8 7 6 5 4 3 2 1 0
The sum: 17

If'n you need to retain the original ordering simply copy the original vector to a temp vector, sorting the temp.

[Ganado]

In a generalized "top n sum" function, sorting I assume is more efficient if n > log2(vec.size()). [And sorting might be better anyway for many datasets due to caching/branch prediction]

[mbozzi]

No reason to fully sort the array, not that it makes much difference when it's so small.

Other choices might rely on std::nth_element or std::partial_sort

#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>

int main()
{
  std::array vec { 5, 7, 4, 2, 8, 6, 1, 9, 0, 3 };
  
  auto const begin = vec.begin();
  auto const pivot = vec.end() - 2;
  auto const end   = vec.end();
  
  std::nth_element(begin, pivot, end);  
  std::cout << "maximum sum = " << std::accumulate(pivot, end, 0);
}

What is the optimal solution here considering time complexity?

To find the maximum sum of k = 2 elements optimal time complexity is Theta(n) where n is the size of the array.

Even if k isn't asymptotically constant the answer is still O(n), because one can use a suitable selection algorithm, see:
https://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_selection