sam

A sequence is given of positive integers N and one number K. Let all numbers of the sequence is highlighted a0 to an-1. First To define the sum of absolute differences as abs (a1-a0) + abs (a2-a1) + ... + abs (aN-1-aN-2). To choose exactly K consecutive numbers of the sequence, so that when you merge into one sequence, the sum of absolute differences is the maximum. Print this amount.

Input: The first line you are given two numbers N (1≤N≤100) and K (1≤K≤100, K≤N). In the second line you are given N positive integers, each number is less than 1,000.

Output: To print the required maximum sum of absolute differences.

Note: The numbers are taken in the order in which they are given in the first row. Do not change the order of the numbers in the new sequence.

Name of the class (Java): SumOfAbsoluteDifferences.

A partial solution: The task is considered solved if partly spent 5 test examples.


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

public class SumOfAbsoluteDifferences {

        static int solve(int a[], int n, int k)
        {
                int[][] mat = new int[a.length][k];
                int rez = 0;

                for (int i = 1; i < n; i++)
                {
                        for (int j = 1; j < k; j++)
                        {
                                for (int k1 = 0; k1 < i; k1++)
                                {
                                        int raz = Math.abs(a[i] - a[k1]);
                                        if (mat[i][j] < mat[k1][j-1] + raz)
                                                mat[i][j] = mat[k1][j-1] + raz;
                                        //System.out.printf("%d - %d = %d\n", a[i], a[k1], raz);
                                }
                                //System.out.println("--------------------------------");
                                if (mat[i][j] > rez) rez = mat[i][j];
                        }
                }
        /*
                for (int i = 0; i < n; i++)
                {
                        for (int j = 0; j < k; j++)
                                System.out.print(mat[i][j] + " ");
                        System.out.println("");
                }*/
                return rez;
        }

        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());
                }

                int res = solve(numbers, N, K);
                System.out.println(res);

                br.close();

        }

}


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

Sample output
16