一道OJ上的题，数的划分，求大神解答

Question

有N个排列好的数，不改变排列次序，要分成K个部分，每个部分至少有一个数， (其中K <=N)，若将每一个部分的数相乘，然后将K个部分相加，则可以得到一个表达式，求这个表达式的最大数值。

输入格式
文件第一行为2个整数N、K
下面N行为N个整数（N<=100，整数的范围都在整型以内）
样例输入
5 2
1
2
3
4
5

样例输出
121

我的思路是动态规划：以f(i,j)表示分成i组，最后一个数是j的最大数值。
以下是我的代码：

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int n,a[101],m,f[101][101];
    int main() {
            cin>>n>>m;
            for (int i=1;i<=n;++i)
                    cin>>a[i];
            for (int i=1;i<=m;++i)
                    for (int j=i;j<=n;++j) {
                            int s=1;
                            for (int k=j-1;k>=i-1;--k) {
                                    s*=a[k+1];
                                    f[i][j]=max(f[i][j],f[i-1][k]+s);
                            }
                    }
            cout<<f[m][n];
            return 0;
    }

Answer 1

给一个死算的版本，供你校验结果，C#写的。

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 1, 2, 3, 4, 5 };
            var query = Split(arr, 2);
            int max = 0;
            foreach (var item in query)
            {
                // Console.WriteLine(string.Join("|", item.Select(x => string.Join(", ", x))));
                int r = item.Sum(x => x.Aggregate(1, (a, b) => a * b));
                if (max < r) max = r;
            }
            Console.WriteLine(max);
        }
        static IEnumerable<IEnumerable<IEnumerable<int>>> Split(IEnumerable<int> source, int n)
        {
            int[] splitter = Enumerable.Range(1, n - 1).ToArray();
            splitter[n - 2]--;
            int[] lastsp = Enumerable.Range(source.Count() - n, n -1).ToArray();
            while (splitter.Zip(lastsp, (x, y) => x != y).Any(x => x == true))
            {
                for (int i = n - 2; i >= 0; i--)
                {
                    if (splitter[i] < lastsp[i])
                    {
                        splitter[i]++;
                        for (int j = i + 1; j < n - 1; j++)
                        {
                            splitter[j] = splitter[i] + j - i;
                        }
                        break;
                    }
                }
                IEnumerable<int>[] result = new IEnumerable<int>[n];
                int acc = 0;
                for (int i = 0; i < n; i++)
                {
                    if (i == n - 1)
                    {
                        result[i] = source.Skip(acc);
                    }
                    else
                    {
                        result[i] = source.Skip(acc).Take(splitter[i] - acc);
                        acc = splitter[i];
                    }
                }
                yield return result;
            }
        }
    }
}