C实现****************************

#include <stdio.h>

#include <stdlib.h>

int main()

{

   int n,k,i,a[100],dp[100][100],sum=0;

   scanf("%d%d",&n,&k);

   for(i=1;i<=n;i++)

   {

       scanf("%d",&a[i]);

       sum+=a[i];

       dp[i][0]=sum;

   }

    for(int i=1;i<=n;i++)//n个数

    {

        for(int j=1;j<=i-1;j++)//最多有i-1个乘号，数量级较小，就不剪枝了

        {

            for(int p=2;p<=i;p++)//第j个乘号插入的位置，如果和前面的乘号位置重叠了，也不影响，还是原来的dp[i][j]

            {

                dp[i][j]=max(dp[i][j],dp[p-1][j-1]*(dp[i][0]-dp[p-1][0]));//从车如位置到i的和，一起乘总比一个乘要大

            }

        }

    }

    printf("%d",dp[n][k]);

    return 0;

}

int max(int a,int b)

{

    if(a>b)

        return a;

    else

        return b;

}