Skip to content

Instantly share code, notes, and snippets.

@gtke
Created March 28, 2014 04:22
Show Gist options
  • Save gtke/9825371 to your computer and use it in GitHub Desktop.
Save gtke/9825371 to your computer and use it in GitHub Desktop.
//package DynamicProgramming;
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner s = new Scanner(System.in);
String m = "";
int n = s.nextInt();
int[][] arr = new int[n][n];
int maxNum = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
arr[i][j]=s.nextInt();
}
}
int ans=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
int [] sum = new int[n];
for(int j=i;j<n;j++){
int max=Integer.MIN_VALUE;
int tmp=0;
for(int l=0;l<n;l++){
sum[l]+=arr[j][l];
tmp+=sum[l];
max=Math.max(max, tmp);
if(tmp<0)
tmp=0;
}
ans=Math.max(max, ans);
}
}
System.out.println(ans);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment