coding/maximum sum.cpp at master · chayankumar999/coding · GitHub

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100][100],a1[100][100],arr[100][100];
int main()
{
    ll n,i,j,k,r,c;
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                {
                    cin>>a[i][j];
                }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                {
                    a1[i][j]=a[i][j]+a1[i-1][j];
                }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                arr[i][j]=arr[i][j-1]+a1[i][j];
            }
        }
        ll maxx=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                for(k=i-1;k>=0;k--)
                {
                    for(r=j-1;r>=0;r--)
                    {
                        ll x=arr[i][j]+arr[k][r]-arr[k][j]-arr[i][r];
                        if(x>maxx)
                        {
                            maxx=x;
                        }
                    }
                }
            }
        }
        cout<<maxx<<endl;

    }
    return 0;
}