2013
11-11

# Sumsets

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

For each S, a single line containing d, or a single line containing “no solution”.

5
2
3
5
7
12
5
2
16
64
256
1024
0


12
no solution


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
* Accepted.
*
*
*/
public class Main {

private static Set< Long> set = new HashSet< Long>();

private static Map< Long, List< String>> map = new HashMap< Long, List< String>>();

private static Set< Long> sumSet = new HashSet< Long>();

/**
* @param args
*/
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (true) {
int n = cin.nextInt();

if (n == 0) {
break;
}

set.clear();
sumSet.clear();

map = new HashMap< Long, List< String>>();

int[] a = new int[n];

for (int i = 0; i < n; i++) {
a[i] = cin.nextInt();

}

Arrays.sort(a);

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] != a[j]) {
long temp = a[i];
temp += a[j];
}
}
}

for (int i = n - 1; i >= 0; i--) {
for (int j = i - 1; j >= 0; j--) {

if (a[i] == a[j]) {
continue;
}

long v = a[i];
v -= a[j];

if (!sumSet.contains(v)) {
// System.out.println("v=" + v);
continue;
}

List list = map.get(v);

if (list == null) {
list = new ArrayList();
list.add("" + a[i] + " " + a[j]);
} else {

list.add("" + a[i] + " " + a[j]);
}

map.put(v, list);
}
}
int ans = 0;
boolean find = false;

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i] == a[j]) {
continue;
}

long sum = a[i];
sum += a[j];
List< String> list = map.get(sum);
// System.out.println("list=" + list);

if (list != null) {
for (String s : list) {

String[] ss = s.split("[ ]+");

int d = Integer.parseInt(ss[0]);
int c = Integer.parseInt(ss[1]);

if (d != a[i] && d != a[j] && c != a[i] && c != a[j]) {
find = true;
ans = Math.max(ans, d);
}
}
}
}
}

if (find) {
System.out.println(ans);
} else {
System.out.println("no solution");
}
}
}
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

2. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。