SPOJ Problem TMSUM

THE MAXIMIZE SUM

Explanation:

Given 'n' number of elements in a set, you need to find the subsets of the set containing maximum of two elements and minimum of one. Once, we have the subsets, we need to find the product of the elements in the subset containing two elements. And, then adding all the found products to the elements of set with size one. Following the process, we need to find the maximum sum at the end and then print. The problem requires li'l bit of recursion which later gets converted into a very simple DP problem. You can find the explanation below.

Now, since we are supposed to find the maximum sum, thus, we can say that the product of two numbers should be maximum (as we are adding the product of two numbers for a 2-element set to get the sum). For that, we need to multiply together, the largest numbers and hence, we can get maximum product. Thus, we can come to a conclusion that, sorting is required here. Once sorted, we have two options now, either we form a 2-element set or 1-element set containing this element.

Let's say, for example.

Set, S = {1, 3, 2}
Once, we have sorted this, we get S' = {1, 2, 3}.

Now, taking every element into consideration, we can have following possible subset combinations.

1. {1}, {2}, {3}
2. {1}, {2, 3}
3. {1, 2}, {3}

Calculating results for above possible combination, we get,

1. 6
2. 7
3. 5

And, as said above, we need to find the product of largest numbers to get the maximum sum, and thus, we can see, we get the maximum sum for case 2, where we find the product of two largest numbers.

Now, let's try to come up with the recursion formula.

Case 1.
Consider, we take ith element ai into a 1-element set, so the sum till ith index, say Si, will be, Si = Si-1 + ai, where Si-1 is the maximum sum till index (i-1).

Case 2.
Consider, we take ith element ai into a 2-element set, so the sum till ith index, say Si, will be, Si = Si-2 + (ai * ai-1), where Si-2 is the maximum sum till index (i-2).

So, the final formula becomes,

Si = max(Si-1 + ai, Si-2 + (ai * ai-1))

Below is the code for reference.

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

int main(){
 
    int t, n, arr[100];
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=0;i<n;i++)
            scanf("%d", &arr[i]);
        if(n == 1){
            printf("%d\n", arr[0]);
            continue;
        }
        if(n == 2){
            printf("%d\n", max(arr[0] * arr[1], arr[0] + arr[1]));
            continue;
        }
        sort(arr, arr + n);
        int sum[100];
        sum[0] = arr[0];
        sum[1] = max(arr[0] * arr[1], arr[0] + arr[1]);
        for(int i=2;i<n;i++)
            sum[i] = max(sum[i-1] + arr[i], sum[i-2] + (arr[i-1] * arr[i]));
        printf("%d\n", sum[n-1]);
    }
    return 0;
}

Any suggestions are welcome.