1 首先学到的是 求一维数组最大子段和! 这个的想法很简单,只要大家多动几次笔,想想就会理解了!
2 我卡住的地方是,为什么如果 <= 0 就从新开始 然道 <= 0 这个子段中任意数字重新开始新的子段就没有最大的?
3 最后想想就明白了!
4
5 int p( int *s2,int c1 )
6 {
7 int max = -1000;
8 int sum = 0;
9 for ( int i = 0; i != c1; ++i ) // 一维数组 最大 子段和
10 {
11 if ( sum > 0 )
12 sum += s2[i];
13 else sum = s2[i];
14 if ( sum > max )
15 max = sum;
16 }
17 }
18
19 然后做了到题目,求矩阵的最大子矩阵的和! 它的思想和一维是一样的!
20
21 #include <cstdio>
22
23 int p( int *s2,int c1 )
24 {
25 int max = -1000;
26 int sum = 0;
27 for ( int i = 0; i != c1; ++i ) // 一维数组 最大 子段和
28 {
29 if ( sum > 0 )
30 sum += s2[i];
31 else sum = s2[i];
32 if ( sum > max )
33 max = sum;
34 }
35 return max;
36 }
37
38 int main()
39 {
40 int r,c;
41 scanf ( "%d",&r );
42 int s1[500][500];
43 for ( int i = 0; i != r; ++i )
44 for ( int j = 0; j != r; ++j )
45 scanf ( "%d\n",&s1[i][j] );
46 int b[500];
47 int max = -1000;
48 int max1;
49 for ( int i = 0; i != r; ++i ) //控制起始行
50 {
51 for ( int b1 = 0; b1 != r; ++b1 )
52 b[b1] = 0;
53 for ( int j = i; j != r; ++j ) // 控制行数 从 i 起始 到最后一行;
54 {
55 for ( int k = 0; k != r; ++k )
56 b[k] += s1[j][k];
57 max1 = p( b,r );
58 if ( max1 > max )
59 max = max1;
60 }
61 }
62 printf ( "%d\n",max );
63 return 0;
64 }
65
66