fork download
copy 
  1. /*
  2. https://w...content-available-to-author-only...f.com/problems/MMSUM
  3. */
  4.  
  5. #include<iostream>
  6. #include<cstdio>
  7. #include<vector>
  8. #include<climits>
  9.  
  10. #define lli long long int
  11. #define scan(z) scanf("%lld",&z);
  12. #define print(z) printf("%lld\n",z);
  13.  
  14. using namespace std;
  15.  
  16. lli maxSubTreeFor(vector<lli> &a, int l,int h,lli curr_sum,lli max_so_far) {
  17.     lli max_remd=LONG_LONG_MIN;
  18.     for(int i=l;i<=h;i++) {
  19.         if(a[i]<0) {
  20.             lli cs=curr_sum;
  21.             lli msf=max_so_far;
  22.             for(int j=i+1;j<=h;j++) {
  23.                 if(a[j]>cs+a[j])
  24.                     break;
  25.                 else
  26.                     cs=cs+a[j];
  27.                 msf=max(cs,msf);
  28.             }
  29.             max_remd=max(max_remd,msf);
  30.         }
  31.  
  32.         curr_sum=max(a[i],curr_sum+a[i]);
  33.         max_so_far=max(max_so_far,curr_sum);
  34.     }
  35.  
  36.     return max(max_remd,max_so_far);
  37. }
  38.  
  39. lli maxSubTreeLeftRight(vector<lli> &a, int l,int h,lli curr_sum,lli max_so_far) {
  40.     lli max_remd=LONG_LONG_MIN;
  41.     for(int i=l;i<=h;i++) {
  42.         if(a[i]<0) {
  43.             lli cs=curr_sum;
  44.             lli msf=max_so_far;
  45.  
  46.             curr_sum=max(a[i],curr_sum+a[i]);
  47.             max_so_far=max(max_so_far,curr_sum);
  48.  
  49.             for(i+=1;i<=h;i++) {
  50.                 if(a[i]>cs+a[i])
  51.                     break;
  52.                 else
  53.                     cs=cs+a[i];
  54.                 msf=max(cs,msf);
  55.  
  56.                 curr_sum=max(a[i],curr_sum+a[i]);
  57.                 max_so_far=max(max_so_far,curr_sum);
  58.             }
  59.             max_remd=max(max_remd,msf);
  60.             //cout<<max_remd<<" "<<max_so_far<<" asf\n";
  61.         }
  62.  
  63.         if(i>h)
  64.             break;
  65.  
  66.         curr_sum=max(a[i],curr_sum+a[i]);
  67.         max_so_far=max(max_so_far,curr_sum);
  68.     }
  69.  
  70.     lli left=max(max_remd,max_so_far);
  71.     curr_sum=max_so_far=a[h];
  72.     for(int i=h-1;i>=l-1;i--) {
  73.         if(a[i]<0) {
  74.             lli cs=curr_sum;
  75.             lli msf=max_so_far;
  76.  
  77.             curr_sum=max(a[i],curr_sum+a[i]);
  78.             max_so_far=max(max_so_far,curr_sum);
  79.  
  80.             for(i-=1;i>=l-1;i--) {
  81.                 if(a[i]>cs+a[i])
  82.                     break;
  83.                 else
  84.                     cs=cs+a[i];
  85.                 msf=max(cs,msf);
  86.  
  87.                 curr_sum=max(a[i],curr_sum+a[i]);
  88.                 max_so_far=max(max_so_far,curr_sum);
  89.             }
  90.             max_remd=max(max_remd,msf);
  91.             //cout<<max_remd<<" "<<max_so_far<<" asf\n";
  92.         }
  93.  
  94.         if(i<l-1)
  95.             break;
  96.  
  97.         curr_sum=max(a[i],curr_sum+a[i]);
  98.         max_so_far=max(max_so_far,curr_sum);
  99.     }
  100.  
  101.  
  102.     return max(left,max(max_remd,max_so_far));
  103. }
  104.  
  105. lli maxSubArray(vector<lli> &a, int l,int h) {
  106.     if(l>h)
  107.         return 0;
  108.  
  109.     lli curr_sum=a[l],max_so_far=a[l];
  110.     int s=0,ns=0,e=0;
  111.     lli m=0,mm=min(a[l],(lli)0);
  112.     for(int i=l+1;i<=h;i++) {
  113.  
  114.         if(a[i] > curr_sum+a[i]) {
  115.             ns=i;
  116.             mm=0;
  117.             curr_sum=a[i];
  118.         }
  119.         else {
  120.             mm=min(mm,a[i]);
  121.             curr_sum=curr_sum+a[i];
  122.         }
  123.  
  124.         if(curr_sum > max_so_far) {
  125.             m=min(mm,m);
  126.             s=ns;
  127.             e=i;
  128.             max_so_far=curr_sum;
  129.         }
  130.     }
  131.  
  132.     lli left=max_so_far;
  133.     lli sum=max_so_far;
  134.     for(int i=s-2;i>=l;i--) {
  135.         sum+=a[i];
  136.         if(sum>left)
  137.             left=sum;
  138.     }
  139.     lli right=max_so_far;
  140.     sum=max_so_far;
  141.     for(int i=e+2;i<=h;i++) {
  142.         sum+=a[i];
  143.         if(sum>right)
  144.             right=sum;
  145.     }
  146.  
  147.     lli mid=max_so_far;
  148.     if(s<e)
  149.         mid-=m;
  150.  
  151.     lli res=max(mid,max(max_so_far,max(left,right)));
  152.  
  153.     //cout<<"start "<<s<<" "<<e<<" "<<m<<"\n";
  154.  
  155.     return res;
  156. }
  157.  
  158. /*
  159. 8
  160. 9
  161. 10 10 -10 10 12 20 -10 10 5
  162. 8
  163. 1 -100 -10 8 4 -3 2 6
  164. 8
  165. 10 -100 10 7 -2 5 -10 6
  166. 8
  167. 6 -10 5 -2 7 10 -100 10
  168. 5
  169. 1 -2 3 -2 5
  170. 2
  171. -1 -2
  172. 7
  173. 1 -2 7 -2 5 -10 6
  174. 7
  175. 1 -2 3 -2 5 -10 6
  176.  
  177.  
  178. */
  179. int main() {
  180.     int t;
  181.     cin>>t;
  182.     //cout<<t;
  183.     int n;
  184.     while(t--) {
  185.         //cout<<"loop in "<<t;
  186.         cin>>n;
  187.         vector<lli> a(n);
  188.         lli x;
  189.         for(int i=0;i<n;i++) {
  190.             cin>>x;
  191.             a[i]=x;
  192.         }
  193.  
  194.         /*vector<int> mids;
  195.         //mids.push_back(0);
  196.         lli m=0;
  197.         for(int i=1;i<n;i++) {
  198.             if(a[i]==m)
  199.                 mids.push_back(i);
  200.             else if(a[i]<m) {
  201.                 //m=a[i];
  202.                 mids.clear();
  203.                 mids.push_back(i);
  204.             }
  205.         }
  206.  
  207.         lli ret=maxsubarray(a,n);
  208.         int mil=mids.size();
  209.         for(int i=0;i<mil;i++) {
  210.             int index=mids[i];
  211.  
  212.             lli val=a[index];
  213.             int start=0,end=0;
  214.             a.erase(a.begin()+index);
  215.             ret=max(ret,maxsubarray(a,n-1),start,end);
  216.             if(index>=start && index<=end)
  217.  
  218.             a.insert(a.begin()+index,val);
  219.         }*/
  220.  
  221.         lli ret=maxSubArray(a,0,n-1);
  222.         //lli ret=maxSubTreeFor(a,1,n-1,a[0],a[0]);
  223.         //lli ret=maxSubTreeLeftRight(a,1,n-1,a[0],a[0]);
  224.  
  225.         //print(ret);
  226.         cout<<ret<<endl;
  227.         //cout<<"loop out "<<t;
  228.     }
  229. }
  230.  
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
8
9
10 10 -10 10 12 20 -10 10 5
8
1 -100 -10 8 4 -3 2 6
8
10 -100 10 7 -2 5 -10 6
8
6 -10 5 -2 7 10 -100 10
5
1 -2 3 -2 5
2
-1 -2
7
1 -2 7 -2 5 -10 6
7
1 -2 3 -2 5 -10 6
stdout
copy 
67
20
30
30
8
-1
16
12
https://ideone.com/EmrUAl
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!