设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘机称I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大乘积。

/*
 * 最大k乘积
题目描述
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘机称I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大乘积。

输入描述
第一行有两个整数n和k。整数n是序列的长度，整数k是分割的段数。在接下来的一行中是一个n位十进制整数（n<=10）

输出描述
第一行的数是计算出的最大k乘积。

输入样例
2 1
15

输出样例
15
 */
package exam4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author 朱小波
 */
public class Test1 {

    long arrayX[][] = new long[50][10];
    long arrayY[][] = new long[50][10];

    public long maxResult(int n, int k) {
        int i, j, d, s;
        long temp, max;
        for (i = 1; i <= n; i++) {
            arrayX[i][1] = arrayY[1][i];
        }
        for (i = 1; i <= n; i++) {
            for (j = 2; j <= k; j++) {
                if (i >= j) {
                    max = 0;

                    for (d = 1; d < i; d++) {
                        if ((temp = arrayX[d][j - 1] * arrayY[d + 1][i]) > max) {
                            max = temp;
                        }
                    }
                    arrayX[i][j] = max;


                }
            }
        }

        return arrayX[n][k];

    }

    public static void main(String[] args) {
        int[] date;
        int i, j;
        int a[] = new int[50];
        Test1 test = new Test1();
        date = InOutPut.inPutInt(" ");//n date[0],k date[1]
        String dat = InOutPut.inPutString();
        for (int k = 1; k <= dat.length(); k++) {
            a[k] = Integer.parseInt(String.valueOf(dat.charAt(k - 1)));
        }
        for (i = 1; i <= date[0]; i++) {
            test.arrayY[i][i] = a[i];
            for (j = i + 1; j <= date[0]; j++) {
                test.arrayY[i][j] = test.arrayY[i][j - 1] * 10 + a[j];
            }

        }
        System.out.println(test.maxResult(date[0], date[1]));

    }
}

class InOutPut {

    /**
     * @return 已s隔开字符串存到数组中
     * @输入
     */
    public static String[] inPutString(String s) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        try {
            str = br.readLine();
        } catch (IOException ex) {
            Logger.getLogger(InOutPut.class.getName()).log(Level.SEVERE, null, ex);
        }
        String strArray[] = str.split(s);
        return strArray;
    }

    /**
     * @return 字符串
     * @输入
     */
    public static String inPutString() {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        try {
            str = br.readLine();
        } catch (IOException ex) {
            Logger.getLogger(InOutPut.class.getName()).log(Level.SEVERE, null, ex);
        }
        return str;
    }

    /**
     *
     * @return 整数已s隔开字符串存到数组中
     */
    public static int[] inPutInt(String s) {
        String strArray[] = InOutPut.inPutString(s);
        int intArray[] = new int[strArray.length];
        for (int i = 0; i < strArray.length; i++) {
            intArray[i] = Integer.parseInt(strArray[i]);
        }
        return intArray;
    }

    /**
     *
     * @return 输入整数
     */
    public static int inPutInt() {
        Scanner sc = new Scanner(System.in);
        return sc.nextInt();
    }

    /**
     * 输出
     */
    static void outPutString(String str[]) {
        for (int i = 0; i < str.length; i++) {
            System.out.print(str[i] + " ");

        }
    }

    static void outPutInt(int intArray[]) {
        for (int i = 0; i < intArray.length; i++) {
            System.out.print(intArray[i] + " ");

        }
    }
}