maximum_frequent_sum, C++ (gcc)

maximum_frequent_sum

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long int l;
#define pb push_back
#define ppb pop_back
#define pb push_back
#define mp make_pair
#define loop(n1) for(ll i=0;i<n1;i++)
#define debug(n) cout<<n<<endl
#define mod 1000000007
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
void swap(int *x, int *y)
{
	int t=*x;
	*x=*y;
	*y=t;
	}
long long int pow(long long int a,long long int b)
{
	long long int res=1;
	while(b)
	{
		if(b%2==1)
			res=(res*a)%mod;
		b=b/2;
		a=(a*a)%mod;
	}
	return res;
}
int lcs(string s1, string s2,int n, int m)
    {
        long int t[n+1][m+1],i,j;
        memset(t,-1,sizeof(t));
        //initialise
        for(i=0;i<n+1;i++)
            for(j=0;j<m+1;j++)
                if(i==0||j==0)  t[i][j]=0;
        
        for(i=1;i<n+1;i++)
        {
            for(j=1;j<m+1;j++)
            {
                if(s1[i-1]==s2[j-1])
                t[i][j]=1+t[i-1][j-1];
                else
                t[i][j]=max(t[i-1][j],t[i][j-1]);
            }
        }
       return t[n][m]; 
}
int knapSack(int w, int wt[], int val[], int n) 
    { 
       long int t[n+1][w+1],i,j;
       memset(t,-1,sizeof(t));
       // initialize the matrix
       for(i=0;i<n+1;i++)
       {
           for(j=0;j<w+1;j++)
           {
               if(i==0||j==0) t[i][j]=0;
           }
       }
       //code
       for(i=1;i<n+1;i++)
       {
           for(j=1;j<w+1;j++)
           {
               if(wt[i-1]<=j)
               t[i][j]=max(val[i-1]+t[i-1][j-wt[i-1]],t[i-1][j]);
               else
               t[i][j]=t[i-1][j];
           }
       }
    
        return t[n][w];
    }
ll findSubarray(int arr[], int n,int target ) {
        ll ans=0;
        unordered_map<ll,ll> m;
        int sum=0,i;
        m[0]=1;
        
        for(i=0;i<n;i++)
        {
            sum+=arr[i];
            if(m.find(sum-target)!=m.end())
            {
                ans+=m[sum-target];
                
            }
            m[sum-target]++;
        }
        return ans;
    }
int num(char c)
{
    if(c=='1') return 1;
    else if(c=='2') return 2;
    else if(c=='3') return 3;
    else if(c=='4') return 4;
    else if(c=='5') return 5;
    else if(c=='6') return 6;
    else if(c=='7') return 7;
    else if(c=='8') return 8;
    else if(c=='9') return 9;
    return 0;
}
char ch(int n)
{
    if(n==1) return '1';
    else if(n==2) return '2';
    else if(n==3) return '3';
    else if(n==4) return '4';
    else if(n==5) return '5';
    else if(n==6) return '6';
    else if(n==7) return '7';
    else if(n==8) return '8';
    else if(n==9) return '9';
    return '0';
}
int main()
{	//init_code();
	int t;
    cin>>t;
    while(t--)
    {
        long long int max_so_far=0;
        map<long int,long int> m;
        long int n;
        cin>>n;
        long int count=0;
        long int arr[n];
        loop(n) cin>>arr[i];
        for(int i=0;i<n;i++)
        {   //(arr[i]==0) count++;
            max_so_far=max_so_far+arr[i];
            if(max_so_far<0)
            {
                max_so_far=0;
            }
            else
            {
                m[max_so_far]++;
            }
        }
        long int  max_val=0,max_freq=1;
        for(auto p:m)
        {
            if(p.second>=max_freq)
            {
                max_freq=p.second;
                max_val=p.first;
            
            }
            // cout<<p.first<<" "<<p.second<<endl;
            
        }
        cout<<max_val*(max_freq-count)<<endl;
    }

return 0;
}


run \| edit \| history \| help	0