[ADS] WeightedSum (Solved)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class WeightedSum {
    static int UNDEFINED = 0;

    static int other(int numbers[], int N, int K) {
        int i, j, k;

        int opt[][] = new int[N][K + 1];

        for (i = 0; i < N; i++) {
            for (j = 0; j <= K; j++) {
                opt[i][j] = UNDEFINED;
            }
        }

        opt[0][1] = numbers[0];
        int res = 0;

        for (i = 1; i < N; i++) {
            opt[i][1] = numbers[i];
            for (j = 2; j <= K; j++) {
                for (k = 0; k < i; k++) {
                    if (opt[i][j] == UNDEFINED) {
                        if (opt[k][j - 1] != UNDEFINED) {
                            opt[i][j] = opt[k][j - 1] + numbers[i] * j;
                        }
                    } else {
                        if (opt[k][j - 1] != UNDEFINED) {
                            opt[i][j] = Math.max(opt[i][j], opt[k][j - 1] + numbers[i] * j);
                        }
                    }
                }
            }
            res = Math.max(res, opt[i][K]);
        }
        int index = i;

        for (i = 0; i < N; i++) {
            for (j = 0; j < K + 1; j++) {
                System.out.print(opt[i][j] + " ");
            }
            System.out.print("\n");
        }

        return res;
    }

/*
Sample input
10 3
1 9 2 3 6 1 3 2 1 3

Sample output
37
*/

    /* 1⋅првиотброј+2⋅вториотброј+…+K⋅K−тиотброј */
    static int solve(int numbers[], int len, int choose) {
        int matrix[][] = new int[len][choose + 1];
        int result = 0;
        int UNDEFINED = -1;

        for (int i = 0; i < len; i++) {
            matrix[i][1] = numbers[i];
        }

        for (int i = 1; i < len; i++) {
            for (int j = 2; j < choose + 1; j++) {
                for (int k = 0; k < i; k++) {
                    if (matrix[i][j] == UNDEFINED) {
                        //if (matrix[k][j - 1] != UNDEFINED) {}
                        matrix[i][j] = matrix[k][j - 1] + numbers[i] * j;

                    } else if (matrix[i][j] != UNDEFINED) {
                        /* Meaning it is defined */
                        matrix[i][j] = Math.max(matrix[i][j], matrix[k][j - 1] + numbers[i] * j);
                    }
                }
                result = Math.max(result, matrix[i][j]);
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.print("\n");
        }

        return result;
    }

    public static void main(String[] args) throws Exception {
        int i, j, k;

        /*BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int numbers[] = new int[N];

        st = new StringTokenizer(br.readLine());
        for (i=0;i<N;i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        br.close();*/
        int N = 10;
        int K = 3;
        int numbers[] = {1, 9, 2, 3, 6, 1, 3, 2, 1, 3};
        int res = solve(numbers, N, K);
        System.out.println("RESULT " + res);

        res = other(numbers, N, K);
        System.out.println("RESULT " + res);


    }

}