去哪儿9.14Java第一题被3整除的最大数
A了,但代码有点多,可以打磨优化一下,有点类似最佳买卖股票时机含冷冻期
public static String getString(int[] d) { int n = d.length; Arrays.sort(d); long[][] dp = new long[3][n + 1]; dp[1][0] = -1; dp[2][0] = -1; for (int i = 1; i <= n; i++) { int index = n - i; if (d[index] % 3 == 0) { dp[0][i] = Math.max(dp[0][i - 1], dp[0][i - 1] * 10 + d[index]); dp[1][i] = dp[1][i - 1]; if (dp[1][i - 1] != -1) { dp[1][i] = Math.max(dp[1][i - 1], dp[1][i - 1] * 10 + d[index]); } dp[2][i] = dp[2][i - 1]; if (dp[2][i - 1] != -1) { dp[2][i] = Math.max(dp[2][i - 1], dp[2][i - 1] * 10 + d[index]); } } else if (d[index] % 3 == 1) { dp[0][i] = dp[0][i - 1]; if (dp[2][i - 1] != -1) { dp[0][i] = Math.max(dp[0][i - 1], dp[2][i - 1] * 10 + d[index]); } dp[1][i] = Math.max(dp[1][i - 1], dp[0][i - 1] * 10 + d[index]); dp[2][i] = dp[2][i - 1]; if (dp[1][i - 1] != -1) { dp[2][i] = Math.max(dp[2][i - 1], dp[1][i - 1] * 10 + d[index]); } } else { dp[0][i] = dp[0][i - 1]; if (dp[1][i - 1] != -1) { dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1] * 10 + d[index]); } dp[1][i] = dp[1][i - 1]; if (dp[2][i - 1] != -1) { dp[1][i] = Math.max(dp[1][i - 1], dp[2][i - 1] * 10 + d[index]); } dp[2][i] = Math.max(dp[2][i - 1], dp[0][i - 1] * 10 + d[index]); } } if (d[0] == 0) { return String.valueOf(dp[0][n]); } else { return dp[0][n] == 0 ? "" : String.valueOf(dp[0][n]); } }