C :

#include "stdio.h"
#include "string.h"
int n,m,s;
int a[100001],b[100001],f[100001];
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int main()
{
	int i,j;
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(b,0,sizeof(b));
		memset(f,0,sizeof(f));
		scanf("%d%d",&m,&n);
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		b[0]=0;
		for(i=1;i<=m;i++)
		{
			s=-100000;
			for(j=i;j<=n;j++)
			{
				f[j]=max(f[j-1]+a[j],b[j-1]+a[j]);
				b[j-1]=s;
				if(f[j]>s)
					s=f[j];
			}
		}
		printf("%d\n",s);
	}
	return 0;
}

C++ :

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN 1000000
#define INF 0x7fffffff
int dp[MAXN+10];
int mmax[MAXN+10];
int a[MAXN+10];
int main()
{
    int n,m;
    int i,j,tmp;
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        scanf("%d %d",&m,&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            mmax[i]=0;
            dp[i]=0;
        }
        dp[0]=0;
        mmax[0]=0;
        for(i=1;i<=m;i++)
        {
                tmp=-INF;
                for(j=i;j<=n;j++)
                {
                    dp[j]=max(dp[j-1]+a[j],mmax[j-1]+a[j]);
                    mmax[j-1]=tmp;
                    tmp=max(tmp,dp[j]);
                }
        }
        printf("%d\n",tmp);

    }
    return 0;
}