package com.company;


public class Main {

    public static void main(String[] args) {
        // write your code here
        int[] songslist = {1, 1, 2, 2, 3, 4, 5, 6};
        int travelTime = 23;
        System.out.println(solve(songslist, travelTime));
    }

    private static int solve(int[] input, int n) {
        int dp[][] = new int[n + 1][input.length + 1];
        for (int i = 0; i < input.length + 1; i++) {
            dp[0][i] = 0;// max songs of i songs can be played in 0 time
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;// 0 when list empty for any target
        }
        int temp = 0, case1, case2;
        for (int i = 1; i < input.length + 1; i++) {
            for (int j = 1; j <= n; j++) {
                temp = input[i - 1];
                case1 = 0;
                case2 = 0;
                if (temp == j)
                    case1 = 1;//dp[i][j]=1 adding only if time is exact

                if (temp < j) {
                    case2 = (dp[j - temp][i - 1] == 0) ? -1 : dp[j - temp][i - 1];//adding this only there is a valid dp[j - temp][i - 1] list available
                    case2++;
                }
                dp[j][i] = Math.max(case1, case2);// picking the best of two
                dp[j][i] = Math.max(dp[j][i], dp[j][i - 1]);//finding if the ignoring this song will help
            }
        }
        printmy(dp);
        return dp[n][input.length];
    }

    private static void printmy(int[][] dp) {
        for (int i = 0; i < dp.length; System.out.println(), i++)
            for (int j = 0; j < dp[i].length; j++)
                System.out.print(dp[i][j] + " ");
    }
}