Timus-1146 Maximum Sum

T
Problem NameMaximum Sum
JudgeTimus
Problem Linkhttps://acm.timus.ru/problem.aspx?space=1&num=1146
Algorithms & DSDynamic Programming, Kadane
#include<bits/stdc++.h> using namespace std; typedef long long int ll; #define sf(n) scanf("%lld",&n); #define YES printf("YES\n"); #define NO printf("NO\n"); #define nl printf("\n"); #define PB push_back #define VST(V) sort(V.begin(),V.end()) #define VSTrev(V) sort(V.begin(),V.end(),greater<long long int>()) #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll mat[110][110]; ll cum_sum[110][110]; ll max_sub_rec(ll n,ll m) { for(ll i=0; i<=n; i++)cum_sum[i][0]=0; for(ll j=1; j<=m; j++) { for(ll i=1; i<=n; i++) { cum_sum[i][j]=cum_sum[i-1][j]+mat[i][j]; } } ll ans=-1111111111; for(ll i=1; i<=n; i++) { for(ll j=i; j<=n; j++) { ll sum=0; for(ll k=1; k<=m; k++) { ll val=cum_sum[j][k]-cum_sum[i-1][k]; sum+=val; ans=max(sum,ans); if(sum<0)sum=0; } } } return ans; } int main() { //freopen("1input.txt","r",stdin); fast; ll tcase=1; // cin>>tcase; for(ll test=1; test<=tcase; test++) { ll n; cin>>n; for(ll i=1; i<=n; i++) { for(ll j=1; j<=n; j++) { cin>>mat[i][j]; } } ll ans=max_sub_rec(n,n); cout<<ans<<"\n"; } return 0; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!