开发笔记:二维数组最大子数组和的求解

1 #include<iostream>
2 #include
3 using namespace std;
4
5 FILE *fpRead=fopen("input.txt","r");
6
7 char cgetchar(){
8 char c;
9 fscanf(fpRead,"%c",&c);
10 return c;
11 }
12
13 int getnum(){
14 char c;
15 int num = 0, fuhao = 1;
16 while((c = cgetchar()) != EOF && (‘0‘ > c || ‘9‘ ‘-‘);
17 if(c == ‘-‘) fuhao = -1;
18 else num = c - ‘0‘;
19 while((c = cgetchar()) != EOF && ‘0‘ <= c && ‘9‘ >= c){
20 num = num * 10 + c - ‘0‘;
21 }
22 return num * fuhao;
23 }
24
25 int main ()
26 {
27 int x,y,i,j,m=0,A[100][100];
28
29 x = getnum();
30 y = getnum();
31 if(x>100||y>100)
32 {
33 cout<<"请重新输入：";
34 cin>>x>>y;
35 }
36 for(i=0;i)
37 {
38 for(j=0;j)
39 {
40 A[i][j] = getnum();
41 printf("%d ", A[i][j]);
42 }
43 printf("
");
44
45 }
46 int sum[100]={0},max=0,result=A[0][0];
47
48 for(i=0;i//确定子数组的最大上界（为第i行）
49 {
50 while(m+i//确定子数组有m+i行
51 {
52 //把子数组当成一位数组一样，求最大子数组的和
53 for(j=0;j)
54 {
55 sum[j]=sum[j]+A[m+i][j];
56
57 }
58 max=0;
59 for(j=0;j)
60 {
61 if(max+sum[j]>sum[j])
62 {
63 max=max+sum[j];
64 }
65 else
66 {
67 max=sum[j];
68 }
69 if(max>result)
70 {
71 result=max;
72 }
73 }
74 m++;//是子数组的行数+1
75 }
76 m=0;
77 for(j=0;j)
78 {
79 sum[j]=0;
80 }
81 }
82 cout<<result;
83 return 0;
84 }