/*** Problem: 108 - Maximum Sum*/#include<iostream>#include<iomanip>usingnamespacestd;intmain(){intn=0;intA[101][101]={0};intsums[101][101]={0};while(cin>>n){// read the matrix and create the auxiliary sum matrixfor(inti=1;i<=n;i++){for(intj=1;j<=n;j++){cin>>A[i][j];// each position is the sum of all values in its left to the topsums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+A[i][j];}}// calculate all subsets and save the maximum sum using the auxiliary matrixlonglongintmax_sum=-127;for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){for(intk=i;k<=n;k++){for(intl=j;l<=n;l++){longlongintsum=-127;// calculate the sums of the subsets using the auxiliary matrix// subtracting the areas that are not in the subsetsum=sums[k][l]-sums[i-1][l]-sums[k][j-1]+sums[i-1][j-1];if(sum>max_sum){max_sum=sum;}}}}}cout<<max_sum<<endl;}}
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.