最大子数组三

  1 #include <iostream>
  2 #include <time.h>
  3 #include<string>
  4 #include<fstream>
  5 #define M 3
  6 #define N 4
  7 using namespace std;
  8 
  9 int main()
 10 {
 11     int length[100],num[M][N] = {0},visit[M][N]={0},i=0;//length[100],是把文件中的数组转化为一位数组，visit[M][N]判断联通性，0为未选中，1为选中,2为连通
 12     bool flag = 0;                                      //判断visit[M][N]是否有1存在，存在为O。
 13     int max= 0; 
 14     srand(unsigned((int)time(0)));
 15     ifstream ifile("1.txt");                         //从文件中读出数组
 16     if(! ifile)
 17     {
 18         cout<<"error"<<endl;
 19     }
 20     int word;
 21     while(ifile>>word)
 22     { 
 23         length[i]=word;
 24         i++;
 25     }
 26     int x=0;
 27     cout<<"从文件中读出的数组为："<<endl;
 28     for(int i=0;i<3;i++)
 29     {
 30         for(int j=0;j<4;j++)
 31         {
 32             num[i][j]=length[x];
 33             cout<<num[i][j]<<" ";
 34             x++;
 35         }
 36         cout<<endl;
 37     }
 38     for (int i = 0;i < M;i++)
 39     {
 40         for (int j = 0;j < N;j++)
 41         {
 42              if (num[i][j] >= 0)
 43             {
 44                 visit[i][j] = 1;                           //给大于零的数进行标记
 45             }
 46         }
 47     }
 48     cout<<endl;
 49     for(int i=0;i<M;i++)                               //标记两个相邻的并且有一个负数的两个数相加，并且和为正数的那种情况
 50     {
 51         for (int j=0;j<N;j++)
 52         {
 53             if (visit[i][j] == 1)
 54             {
 55                 if (num[i+1][j]+num[i][j]>0&&visit[i+1][j] == 0)
 56                 {
 57                     visit[i+1][j]= 2;                            
 58                 }
 59                 if (num[i-1][j]+num[i][j]>0&&visit[i-1][j] == 0)
 60                 {
 61                     visit[i-1][j] = 2;    
 62                 }
 63                 if (num[i][j-1]+num[i][j]>0&&visit[i][j-1] == 0)
 64                 {
 65                      visit[i][j-1]=2;        
 66                 }
 67                 if (num[i][j+1]+num[i][j]>0 && visit[i][j+1] == 0)
 68                 {
 69                     visit[i][j+1]=2;    
 70                 }                  
 71             }                        
 72         }
 73     }
 74 
 75     for (int i=0;i<M;i++)
 76     {
 77         for (int j= 0;j< N;j++)
 78         {                
 79             flag = 0;
 80             if (visit[i][j]!=0 &&num[i][j] < 0)
 81             {
 82                 visit[i][j] = 0;
 83                 for (int p = 0;p < M;p++)
 84                 {
 85                     for (int q= 0;q< N;q++)
 86                     {
 87                         if (visit[p][q] != 0)
 88                         {
 89                             if ((visit[p+1][q] <= 0 || visit[p+1][q] > 2)&&      //排除掉负数最小的那种情况
 90                                 (visit[p-1][q] <= 0 || visit[p-1][q] > 2)&&
 91                                 (visit[p][q+1] <= 0 || visit[p][q+1] > 2)&&
 92                                 (visit[p][q-1] <= 0 || visit[p][q-1] > 2))
 93                             {
 94                                 flag=1;
 95                             }
 96                         }                                
 97                     }
 98                 }
 99                 if (flag)
100                 {
101                     visit[i][j] = 2;
102                 }                        
103             }
104         }
105     }
106 
107    for (int i = 0;i < M;i++)
108     {
109         for (int j = 0;j < N;j++)
110         {
111             if (visit[i][j] != 0)
112             {
113                max+= num[i][j];
114             }
115         }
116     }
117     cout <<"请输入这个最大联通数组的和："<< max << endl;
118 }