Max Sum

Problem:  Write a function that returns the max sum of two numbers from an array of integers


int maxSumofTwoNums(int a[]){
...
}


Solution:  Let's start off with a picture.


Pic 1 shows the array a.  In this case, we can see that the correct answer 17, which we get when we add 9 and 8.

One initially obvious way to solve this is to add up all sums, and then output the largest one at the end.  We can do this by starting to iterate with the first number, and then iterate through every other number and keep a biggestSum until we get to the end.  


The code for this solution is:



int maxSumofTwoNums(int a[]){


    int i, j, biggestSum;


    /* Check the error case of needing at least two elements */
    if (a.size < 2) return ERROR;


    /* Initialize biggestSum */
    biggestSum = a[0] + a[1];


    for (i = 0; i < a.size; i++) {
        for ( j = i+1; j < a.size; i++) {
            if (a[i] + a[j] > biggestSum) 
                biggestSum = a[i] + a[j];
        }
    }
    return biggestSum; 
}


Let's check this with the sample array in pic 1.  In this example, biggestSum is initialized to 4.  It then increases to 17 quickly when the 9 and 8 are added, and no sum is bigger.  Also, all possible sums are checked, so it works in this case.  We have a correct solution.


Also, let's check error cases.  We have checked when there are fewer than two elements, so we should be pretty set here.  We have not checked when the sum is more than the int range, but let's address that later.


So now, what is the run time of this function?  Well, we check n + (n-1) + (n-2)...2.  This is an O(n^2) function.  Can we do better?


At first, it appears potentially not.  We need to check every sum, and this does it.  We have essentially developed an NP solution and treated this problem as if it is NP hard (if this sentence does not make sense, just ignore it; NP and P are not necessary to solve this).


One other thought is to sort the array.  This could be done in O(n log n) time -- and then you could return the sum of the first two elements.  This is faster, but requires sorting (and you may not want to change the order).


However, look at the example array again.  Try to see how you knew that 9 and 8 were the biggest number.  Look at how this is determined intuitively.


You probably didn't add up all the sums and return the greatest, as above.  When I did it, I saw that 9 and 8 were the biggest elements and summed them.  This is a key insight.  Essentially, this problem can be reduced to -- "find the two biggest elements in the array."  And, finding each one of these elements is an O(n) solution, which can make the entire solution O(n).


Now, with this, write the code to:
1.  Find the biggest element
2.  Find the second largest element (handle the case of the largest repeated)
3.  Return the sum


Let's also deal with our error case where the sum exceeds the int range by returning a long instead of an int.



long maxSumofTwoNums(int a[]){


    int i, j;
    int biggest, secondBiggest;
    int bigPlace;


    /* Check the error case of needing at least two elements */
    if (a.size < 2) return ERROR;


    /* Initialize biggest and secondBiggest and bigPlace */
    biggestSum = a[0];
    secondBiggest = a[0];
    bigPlace = 0;


    /* Find the biggest num */
    for (i = 1; i < a.size; i++) {
        if (a[i] > biggest) 
            biggest = a[i];
            bigPlace = i;
        }
    }




    /* make sure if the first elem is the biggest, second
     * cannot be in that location */
    if (bigPlace == 0) secondBiggest = a[1];
    /* Find the second biggest num */
    for (j = 0; j < a.size; j++) {
        if (bigPlace != j && a[j] > secondBiggest) 
            secondBiggest = a[j];
        }
    }


    return (biggest + secondBiggest); 
}


This is an O(n) solution now as we iterate through the array a constant number of times (2x).  We also have solved the error case of exceeding the int range.  


This is a good example of where we were able to come up with a better solution by looking at how we intuitively solved a problem, and doing that, instead of thinking about the obvious way for a computer to solve the problem.  And, we got a much better solution this way.


/* Please let me know if you find bugs, or there are alternative solutions.  Thank you, Noah */