Untitled

 avatar
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...