Maximal-sum Subsequence
time limit per test 2 second memory limit per test 256 megabytes
给一个 N×N 的矩阵 M,可以取连续的一段数(必须是横着或者竖着或者斜着,这个矩阵是循环的,具体如下)。要求找到一个子序列,使得这个序列的和最大。
对于 N=8 的矩阵,如下序列都是合法的:
• M2,1,M2,2,M2,3,M2,4,M2,5,M2,6,M2,7,M2,8.
• M2,2,M2,3,M2,4.
• M2,6,M2,7,M2,8,M2,1,M2,2.
• M4,3,M5,3,M6,3,M7,3.
• M1,2,M2,3,M3,4,M4,5.
• M2,4,M3,3,M4,2,M5,1.
• M3,3,M4,2,M5,1,M1,5.
• M5,6.

一个元素不可取多次,取的必须是连续的一段。

可以什么都不取(即答案为 0)。

传送门:EOJ3235

Input

第一行一个数 T (T≤30),表示数据组数。 每一组数据第一行为一个正整数 N (1≤N≤1000)。 接下来 N 行每行 N 个数表示这个矩阵。(每个元素大小在 −32768 到 32767 之间)

Output

每组数据一行表示最大的序列和。

Sample Input

1
2
3
4
5
6
1
4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2

Sample Output

1
24

题解

连续子串和最大问题 要注意的是这里是循环的 所以可能出现中间断掉 首尾连接的情况 这时候怎么办呐? 很简单 一个数列所有和是固定的 那么我们只要再求一次连续子串中和最小的 减一减就能得到首尾相连的子串连接的最大值 再和 普通求的最大子串和比较 至于怎么求连续子串和最小 将所有数组元素取负 就变成了和求最大子串和一样了
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import java.io.*;  
import java.util.*;
public class Main {
public static void main(String[] args) {
FastScanner sc = new FastScanner();
PrintWriter pw = new PrintWriter(System.out);
int t=sc.nextInt();
while (sc.hasNext()) {
int n=sc.nextInt();
int[][]maze=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
maze[i][j]=sc.nextInt();
}
}
int max=0;
for(int i=0;i<n;i++){
int rmax = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int j = 0;j<n;j++){
if(sum>0){
sum+=maze[i][j];
}else{
sum=maze[i][j];
}
if(sum>rmax){
rmax= sum;
}
}
max=Math.max(max,rmax);
}
for(int i=0;i<n;i++){
int rmax = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
int s=0;
for(int j = 0 ;j<n;j++){
s+=maze[i][j];
if(sum>0){
sum+=-maze[i][j];
}else{
sum=-maze[i][j];
}
if(sum>rmax){
rmax= sum;
}
}
max=Math.max(max,s+rmax);
}
for(int i=0;i<n;i++){
int rmax = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int j = 0 ;j<n;j++){
if(sum>0){
sum+=maze[j][i];
}else{
sum=maze[j][i];
}
if(sum>rmax){
rmax= sum;
}
}
max=Math.max(max,rmax);
}
for(int i=0;i<n;i++){
int rmax = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
int s=0;
for(int j = 0 ;j<n;j++){
s+=maze[j][i];
if(sum>0){
sum+=-maze[j][i];
}else{
sum=-maze[j][i];
}
if(sum>rmax){
rmax= sum;
}

}
max=Math.max(max,s+rmax);
}
for(int i=0;i<n;i++){
int rmax = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int j = 0;j<n;j++){
if(sum>0){
sum+=maze[j][(i+j)%n];
}else{
sum=maze[j][(i+j)%n];
}
if(sum>rmax){
rmax= sum;
}
}
max=Math.max(max,rmax);
}
for(int i=0;i<n;i++){
int rmax = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
int s=0;
for(int j=0;j<n;j++){
s+=maze[j][(i+j)%n];
if(sum>0){
sum+=-maze[j][(i+j)%n];
}else{
sum=-maze[j][(i+j)%n];
}
if(sum>rmax){
rmax= sum;
}
}
max=Math.max(max,s+rmax);
}
for(int i=0;i<n;i++){
int rmax = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int j = 0 ;j<n;j++){
if(sum>0){
sum+=maze[j][(i-j+n)%n];
}else{
sum=maze[j][(i-j+n)%n];
}
if(sum>rmax){
rmax= sum;
}
}
max=Math.max(max,rmax);
}
for(int i=0;i<n;i++){
int rmax = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
int s=0;
for(int j = 0 ;j<n;j++){
s+=maze[j][(i-j+n)%n];
if(sum>0){
sum+=-maze[j][(i-j+n)%n];
}else{
sum=-maze[j][(i-j+n)%n];
}
if(sum>rmax){
rmax= sum;
}
}
max=Math.max(max,s+rmax);
}
pw.println(max);
pw.flush();
}
}
}