//最大字段问题和动态规划算法的推广 最大子矩阵
package wkx;

import java.io.IOException;
import java.util.Scanner;

public class Test
{

private static int MaxSum1(int[] a)
	{
		int sum = 0, b = 0;
		for (int i = 0; i < a.length; i++)
		{
			if (b > 0)
			b += a[i];
			else
			b = a[i];
			if (b > sum)
			sum = b;
		}
		return sum;
	}

private static int MaxSum2(int[][] map,int m,int n)
	{
		int sum=Integer.MIN_VALUE;
		for(int i=0;i<m;i++)
		{
			for(int j=i+1;j<m;j++)
			{
				int[] b=new int[n];
				for(int x=i;x<=j;x++)
				{
					for(int y=0;y<n;y++)
					b[y]+=map[x][y];
					int max=MaxSum1(b);
					if(max>sum)
					sum=max;
				}
			}
		}
		return sum;
	}

public static void main(String[] args) throws IOException
	{
		int[][] map=new int[100][100];
		Scanner in=new Scanner(System.in);
		int m=in.nextInt();
		int n=in.nextInt();
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				map[i][j]=in.nextInt();
			}
		}
		System.out.println(MaxSum2(map,m,n));
	}
}

//最大字段问题和动态规划算法的推广 最大m子段问题
package wkx;

import java.io.IOException;
import java.util.Scanner;

public class Test
{

public static void main(String[] args) throws IOException
	{
		Scanner in = new Scanner(System.in);
		System.out.println("len");
		int len = in.nextInt();
		System.out.println("m");
		int m = in.nextInt();
		int[][] map = new int[len+2][len+2];
		int[] a = new int[len + 1];
		System.out.println("输入"+len+"个数");
		for (int i = 1; i <= len; i++)
		{
			a[i] = in.nextInt();
		}

		for(int i=1;i<=m;i++)
		{
			for(int j=i;j<=len;j++)
			{
				map[i][j]=map[i][j-1]+a[j];
				for(int k=i-1;k<=j-1;k++)
				{
					int sum=map[i-1][k]+a[j];
					if(sum>map[i][j])
					{

						map[i][j]=sum;
					}

				}
			}
		}
		int max=0;
		for(int i=m;i<=len;i++)
		{
			if(map[m][i]>max)max=map[m][i];
		}

		System.out.println("长度为"+len+"的最大"+m+"子段和为"+max);
	}
}