Largest sum issue

[leo2008]

Here the method findSumMax must return largest sum of any two elements in given vector of positive numbers. For example, the largest sum of vector {5,9,7,11} is the sum of the elements 9 and 11, which is 20. But my output is 21 instead of 20. What could be wrong here?

#include<iostream>
#include<vector>
using namespace std;
 
class SumMax {
    public:
    static int findSumMax(int x, const vector<int>& num) {
        int SumMaxi = 0,  wnd_sum;
        for(int i = 0; i < num.size()-x; i++) {
            wnd_sum = 0;
            for(int j = i; j < i+x; j++ ) {
                wnd_sum += num[j];
            }
            SumMaxi = max(SumMaxi, wnd_sum);
        }
        return SumMaxi;
    }
};
 
int main(int argc, char* argv[]) {
    cout <<" The maximum sum of size x: "
    << SumMax::findSumMax(3, vector<int>{5, 9, 7, 11}) << endl;
}


OUTPUT: 21

[George P]

This looks like a job for a debugger to step through the execution and inspect the variables at each step.

First pass idea: I might use a different way to find the sum of the two largest elements in a vector, rather brute-squad, using std::sort (without the class overhead):

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

int maxSum(std::vector<int>);

int main(int argc, char* argv[])
{
   std::vector<int> v { 5, 9, 7, 11 };

   std::cout << "Largest sum: " << maxSum(v) << '\n';
}

// work on a copy of the passed vector
int maxSum(std::vector<int> v)
{
   // reverse sort, from highest to lowest
   std::sort(v.rbegin(), v.rend());

   return v[0] + v[1];
}

Largest sum: 20

[leo2008]

I need to implement method findSumMax and use vector inside the class SumMax. do I need to use std::max? I had implemented method that returns the largest sum of any 2 elements in the given vector.

[George P]

My stand-alone function shouldn't be too difficult to adapt to a class method.

I had implemented method that returns the largest sum of any 2 elements in the given vector.

You think you did, yet it returns a bogus value. That indicates your code logic isn't what you think it is. (Been there, done that)

Using a debugger to step through the code would be invaluable to find where things go off the rails.

Learning to use a debugger is just as important as learning the intricacies of C++. Maybe more so.

do I need to use std::max?

As I showed, no. But then how I brute-squad coded my function required a different perspective, using tools (std::sort, vector reverse iterators) already available instead of reinventing "the wheel."

Why are you passing an integer value that modifies finding the sum of the two largest values in a vector? What is the reason x exists?

I do know if I change the passed value I get a different summation. That shouldn't be happening. The sum should be the same no matter what if it is the same vector being passed.

[leo2008]

Below is my modified code with new logic.

#include <iostream>
#include <vector>

using namespace std;

class SumMax
{
public:
    static int findSumMax(std::vector<int>& num, int x)
    {   
        int curr = num[0];
        int element = 0;
        int elementnew;
        int i;
        for(i = 1; i<x; i++)
        {
          
         elementnew = (curr > element) ? curr : element;

         curr = element + num[i];
         element = elementnew;
        }
        
        return ((curr > element) ? curr : element);
     
    }
};


int main()
{
   std::vector<int> num {5, 9, 7, 11};
   SumMax obj;
   std::cout << "The SumMax is: "  << obj.findSumMax(num, num.size());
}



OUTPUT 
The SumMax is: 20

[seeplus]

If you use a std::vector, you don't need to pass the size. Just use.size()

[Duthomhas]

Argh, your variable names hurt the eyes!

Try to read that again after a week.


You have, at least, recognized that you must keep track of the two largest elements. What happens if there are no elements? Or one element? Have you tried varying the order of testing?:

    num {92 2};
    num {2 92};
    num {-92 2};
    num {2 -92};


Here’s my version:

#include <iostream>
#include <string>
#include <vector>


int max_pair_sum( const std::vector<int> & xs )
{
  if (xs.size() < 2)
    return xs.empty() ? 0 : xs[0];

  int largests[2] = { xs[0], xs[1] };
  for (int x : xs)
    if (largests[0] < x)
    {
      largests[1] = largests[0];
      largests[0] = x;
    }
  return largests[0] + largests[1];
}


int main( int argc, char ** argv )
{
  std::vector<int> xs;
  for (int n = 1;  n < argc;  n += 1)
  {
    xs.push_back( std::stoi( argv[n] ) );
  }
  std::cout << max_pair_sum( xs ) << "\n";
}

It was fun. Thanks!

[edit]
BTW, there’s a bug in mine. Can you see it?

[againtry]

#include <iostream>
#include <vector>

int add(int a, int b) { return a + b; }

bool swap(int &a, int &b)
{
    int temp{a};
    if( a > b)
    {
        a = b;
        b = temp;
        return true;
    }
    return false;
}

int main()
{
//    std::vector<int> array{122,117,28,9,1,27,6,111,322};
    std::vector<int> array{5,9,7,11};
    
    int first{array[0]}, second{array[1]};
    swap(first,second);
    int maximum_sum{add(first,second)};
    
    int trial_sum{0};
    for(int i = 2; i < array.size(); i++)
    {
        trial_sum = add(array[i], second);
        
        if( swap(trial_sum, maximum_sum) )
        {
            first = array[i];
            swap(first,second);
        }
    }
    
    std::cout
    << "Maximum: " << first << '+' << second << '=' << maximum_sum << '\n';
    
    return 0;
}

Maximum: 9+11=20
Program ended with exit code: 0

Maximum: 111+112=223
Program ended with exit code: 0

[George P]

leo2008 wrote:

I need to implement method findSumMax and use vector inside the class SumMax.

Why?

If the answer to that is "the instructor requires it" is bad enough, but to cram code into what appears to be a Java framework unnecessarily is downright cruel.

C++ is NOT Java, Java is NOT C++. Either learn C++ or Java. Don't combine the two, the results will end up being horribly written, hard to maintain, Franstein's monster code.

Smothering it in some cheap canned pasta sauce is probably the best thing to do to "C++ written in Java style" code.

C++ code can use classes, classes were one of the original differences between it and C, but it is not a requirement. Use classes only if the solution to your problem warrants it it for ease of creation and clarity of intent.

You've been given two different solutions, neither of which used a class. Learn from that, please.

[leo2008]

Sure George.
@Duthomhas, I haven't tried much test coverage scenarios here. Never thought about one element or none use cases.

[George P]

There are two online tutorials I recommend if you want to learn C++ the proper way:

1. the tutorial here: http://www.cplusplus.com/doc/tutorial/

One thing to note it is no longer being updated, and only deals with C++11 or earlier.

2. Learn C++: https://www.learncpp.com/

This tutorial does get updates, quite frequently, and has material from later C++ standards, including the latest official standard: C++20. Learn C++ is the one to use.

Both are FREE, neither covers ALL of what C++ offers. There is a reference site available that does: https://en.cppreference.com/w/

CPlusPlus has a reference section, but it is outdated as well. http://www.cplusplus.com/reference/

The reference sites are not for beginners. They aren't just C++, C is also targeted.

[leo2008]

@Duthomhas
What is the bug in your code?
If I execute your code, it output 0.

[seeplus]

How are you calling it? The numbers need to be provided on the command line separated by white space. eg

prog 5 9 7 11
20

[againtry]

Doesn't take much to shuffle code around to a class approach. In fact there's merit in doing it this way:

#include <iostream>
#include <vector>

class Solution
{
private:
    std::vector<int> array;
public:
    Solution(std::vector<int>&);
    
    int add(int, int);
    bool swap(int&, int&);
    void solve();
};

Solution::Solution(std::vector<int>& anArray){array = anArray;};

int Solution::add(int a, int b) { return a + b; }
bool Solution::swap(int &a, int &b)
{
    int temp{a};
    if( a > b)
    {
        a = b;
        b = temp;
        return true;
    }
    return false;
}

void Solution::solve()
{
    int first{array[0]}, second{array[1]};
    swap(first,second);
    int maximum_sum{add(first,second)};
    
    int trial_sum{0};
    for(int i = 2; i < array.size(); i++)
    {
        trial_sum = add(array[i], second);
        
        if( swap(trial_sum, maximum_sum) )
        {
            first = array[i];
            swap(first,second);
        }
    }
    std::cout
    << "Maximum: " << first << '+' << second << '=' << maximum_sum << '\n';
}


int main()
{
    std::vector<int> arr_1{122,117,28,9,1,27,6,111,322};
    std::vector<int> arr_2{5,9,7,11};
    
    Solution sol_1(arr_1);
    sol_1.solve();
    
    Solution sol_2(arr_2);
    sol_2.solve();
    
    return 0;
}

Maximum: 122+322=444
Maximum: 9+11=20
Program ended with exit code: 0

[lastchance]

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

int sumBestTwo( vector<int> &V )
{
   partial_sort( V.begin(), V.begin() + 2, V.end(), greater<int>() );
   return V[0] + V[1];
}

int main()
{
   vector< vector<int> > tests = { { 122, 117, 28, 9, 1, 27, 6, 111, 322 }, { 5, 9, 7, 11 } };
   for ( auto &V : tests ) cout << sumBestTwo( V ) << '\n';
}

444
20

[Duthomhas]

@leo2008

C:\Users\Michael\Programming\quux> a.exe
0

C:\Users\Michael\Programming\quux> a.exe 7
7

C:\Users\Michael\Programming\quux> a.exe 5 9 7 20
29

C:\Users\Michael\Programming\quux> a.exe 20 7 9 5
27

C:\Users\Michael\Programming\quux> _

See what (didn’t) happen when I gave it 20 7 9 5 as input?
Can you see how I goofed?

[leo2008]

@Duthomhas Ok, got it. I am clear now and your approach is buggy code :-)
@seeplus I actually directly run using compiler. It looks like I had missed to test the code using cmd line.

[seeplus]

#include <iostream>
#include <string>
#include <vector>

int max_pair_sum(const std::vector<int>& xs) {
    if (xs.size() < 2)
        return xs.empty() ? 0 : xs[0];

    int largests[2] {};

    for (int x : xs)
        x > largests[0] ? ((largests[0] > largests[1] ? largests[1] = largests[0] : 0), largests[0] = x) : x > largests[1] ? largests[1] = x : 0;

    return largests[0] + largests[1];
}

int main(int argc, char** argv) {
    std::vector<int> xs;

    for (int n = 1; n < argc; ++n)
        xs.push_back(std::stoi(argv[n]));

    std::cout << max_pair_sum(xs) << '\n';
}

[leo2008]

Thanks seeplus, looks more optimal code.

[mbozzi]

@lastchance nth_element might be better than partial_sort especially as n grows beyond 2.

nth_element partitions the container, which is good enough for this. Its time complexity is linear in the container's size. Contrast this with partial_sort, which can't be faster than sorting (linearithmic).