Verschiedener Summands-Problem-Greed-Algorithmus ⇐ Java

[Anonymous]

Ich versuche, das Problem der verschiedenen Summanden mit einem Greedy-Algorithmus zu lösen.

Problembeschreibung

Aufgabe. Das Ziel dieses Problems besteht darin, eine gegebene positive ganze Zahl 𝑛 als Summe möglichst vieler paarweise
verschiedener positiver ganzer Zahlen darzustellen. Das heißt, das Maximum 𝑘 zu finden, sodass 𝑛 als
geschrieben werden kann𝑎1 + 𝑎2 + · · · + 𝑎𝑘 wobei 𝑎1, . . . , 𝑎𝑘 sind positive ganze Zahlen und 𝑎𝑖 ̸= 𝑎𝑗 für alle 1 ≤ 𝑖 < 𝑗 ≤ 𝑘.

Eingabeformat. Die Eingabe besteht aus einer einzelnen Ganzzahl 𝑛.
Einschränkungen. 1 ≤ 𝑛 ≤ 10^9.

Ausgabeformat. Geben Sie in der ersten Zeile die maximale Anzahl 𝑘 sodass 𝑛 als Summe
von 𝑘 paarweise unterschiedlichen positiven ganzen Zahlen dargestellt werden kann. Geben Sie in der zweiten Zeile 𝑘 paarweise unterschiedliche positive ganze Zahlen
aus, die in der Summe 𝑛 ergeben (wenn es viele solcher Darstellungen gibt, geben Sie eine davon aus).

Mein Code:

public class DifferentSummands {
private static List optimalSummands(int n) {
List summands = new ArrayList();
int start = 1;
int newNumber = n;

if (n == 2) {
summands.add(2);
return summands;
}

while (true) {
if (summands.contains(newNumber - start)) {
start++;
continue;
} else {
newNumber -= start;
summands.add(start);
start++;
}

if (newNumber == 0) {
return summands;
}
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List summands = optimalSummands(n);
System.out.println(summands.size());

for (Integer summand : summands) {
System.out.print(summand + " ");
}
}
}


Mein Code schlägt fehl, wenn die Eingabe so groß war, dass sie etwa 3,24 Sekunden dauert und die maximal verfügbare Zeit 1,5 Sekunden beträgt.