(UVA) Maximum Sub-sequence Product - Solution
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=728
The solution below used Dynamic Programming to solve this problem. Moreover, once we would be handling very large numbers, it was necessary to use BigInteger class instead of int/long types.
import java.io.*;
import java.util.*;
import java.math.*;
class Main {
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (sc.hasNext()) {
BigInteger max = new BigInteger("-1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
int numNumbers = 0;
int number = sc.nextInt();
ArrayList<Integer> numbers = new ArrayList<>();
while (number != -999999) {
numbers.add(number);
max = max.max(new BigInteger(String.valueOf(number)));
numNumbers++;
number = sc.nextInt();
}
BigInteger[] product = new BigInteger[numNumbers+1];
product[0] = BigInteger.ONE;
for (int i = 1; i <= numNumbers; i++) {
product[i] = product[i-1].multiply(new BigInteger(String.valueOf(numbers.get(i-1))));
max = max.max(product[i]);
}
for (int i = numNumbers; i >= 1; i--) {
for (int j = i-1; j >= 1; j--) {
if (product[j].equals(BigInteger.ZERO)) {
max = max.max(BigInteger.ZERO);
continue;
}
max = max.max(product[i].divide(product[j]));
}
}
bw.write(max+"\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
The solution below used Dynamic Programming to solve this problem. Moreover, once we would be handling very large numbers, it was necessary to use BigInteger class instead of int/long types.
import java.io.*;
import java.util.*;
import java.math.*;
class Main {
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (sc.hasNext()) {
BigInteger max = new BigInteger("-1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
int numNumbers = 0;
int number = sc.nextInt();
ArrayList<Integer> numbers = new ArrayList<>();
while (number != -999999) {
numbers.add(number);
max = max.max(new BigInteger(String.valueOf(number)));
numNumbers++;
number = sc.nextInt();
}
BigInteger[] product = new BigInteger[numNumbers+1];
product[0] = BigInteger.ONE;
for (int i = 1; i <= numNumbers; i++) {
product[i] = product[i-1].multiply(new BigInteger(String.valueOf(numbers.get(i-1))));
max = max.max(product[i]);
}
for (int i = numNumbers; i >= 1; i--) {
for (int j = i-1; j >= 1; j--) {
if (product[j].equals(BigInteger.ZERO)) {
max = max.max(BigInteger.ZERO);
continue;
}
max = max.max(product[i].divide(product[j]));
}
}
bw.write(max+"\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Comments
Post a Comment