I am trying to find the maximum product of two non overlapping palindromic sub-sequences of string s
that we'll refer to as a
and b
. I came up with below code but it's not giving correct output:
public static int max(String s) {
int[][] dp = new int[s.length()][s.length()];
for (int i = s.length() - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i+1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][s.length()-1];
}
For input string "acdapmpomp", we can choose a
= "aca" and b
="pmpmp" to get a maximal product of score 3 * 5 = 15. But my program gives output as 5.
for (int i = s.length() - 1; i >= 0; i--) { dp[i][i] = 1;
shouldn't the initialisation be separated out from the processing loops? – Naman Dec 7 '18 at 5:34