Untitled
user_0112079941
java
3 years ago
1.5 kB
8
Indexable
import java.util.Scanner; public class Main { public static int[] solve(int[] arr) { if (arr == null || arr.length < 1) { return new int[0]; } final int len = arr.length; int[][] dp = new int[len][2]; //initialize dp[0][0] = 0; // length of max seq streak dp[0][1] = -1; // prev index of max seq streak for (int i = 1; i < len; i++) { for (int j = i - 1; j >= 0; j--) { if (arr[i] % arr[j] == 0) { if (dp[i][0] <= dp[j][0] + 1) { dp[i][0] = dp[j][0] + 1; dp[i][1] = j; } } } } int maxLen = 0; int nextIdx = -1; for (int i = 0; i < len; i++) { if (dp[i][0] > maxLen) { maxLen = dp[i][0]; nextIdx = i; } } int[] ans = new int[maxLen + 1]; for (int i = maxLen; i >= 0; i--) { ans[i] = nextIdx + 1; nextIdx = dp[nextIdx][1]; } return ans; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) arr[i] = scanner.nextInt(); int[] sol = solve(arr); System.out.println(sol.length); for (int i : sol) System.out.print(i + " "); } }
Editor is loading...