In this HackerEarth Maximize Array Sum problem, You are given an array A of size N. You can fix any element, say K of the array and all the elements in the array greater than or equal to K become K and all the elements less than K multiplied by -1. You have to find the maximum sum of the array after fixing K.


HackerEarth Maximize Array Sum problem solution


HackerEarth Maximize Array Sum problem solution.

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
long long a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
long long sum=0,ans=LLONG_MIN;
for(int i=0;i<n;i++){
ans=max(ans,sum+a[i]*(n-i));
sum-=a[i];
}
cout<<ans<<"\n";
}
}

Second solution

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 4e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;


int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int t; cin>>t;
assert(t>=1 && t<=100000);
int sum=0;
while(t--) {
int n; cin>>n;
assert(n>=2 && n<=100000);
sum+=n;
assert(sum<=1000000);
ll a[n],sum[n];
ll mx=0;
for(int i=0;i<n;i++) {
cin>>a[i]; assert(a[i]>=0 && a[i]<=1000000);
mx=max(mx,a[i]);
}
sort(a,a+n);
sum[0]=a[0];
for(int i=1;i<n;i++) sum[i]=sum[i-1]+a[i];
ll res=a[0]*(ll)n;
ll prev=a[0];
for(int i=1;i<n;i++) {
if(a[i]==prev) continue;
ll ans=-1LL*sum[i-1];
ans+=1LL*(n-i)*a[i];
prev=a[i];
res=max(res,ans);
}
cout<<res<<endl;
}

return 0;
}