The SmartPhone problem code optimisation

Visit question
I scored 30% which makes the code logically correct. How do I go about correcting TLE for the remaining 70%.

 #include <iostream>
using namespace std;

int main() {
	int n;
	cin>>n;
	long bud[n][2]; //matrix 1st col customer budget and 2nd for the total possible revenue at that budget;
	for(int i=0;i<n;i++)
	{
	cin>>bud[i][0];
	bud[i][1]=0;
	}
	long max=0; //stores the max revenue generated
	for(int i=0;i<n;i++)    //need to opyimise this
	{
	    for(int j=0;j<n;j++)
	    if(bud[j][0]>=bud[i][0])
	    {
	    bud[i][1]+=bud[i][0];
	    if(bud[i][1]>max)
	    max=bud[i][1];
	    }
	}
	cout<<max;
	return 0;
}

Your solution’s complexity is O(n^2). You can do greedily in O(n \cdot log(n) ).

1 Like

You can use this code-

Click
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
	ll int n;
	cin>>n;
	ll arr[n];
	for(ll int i=0;i<n;i++){cin>>arr[i];}
	ll int ans=INT_MIN;
	sort(arr,arr+n);
	for(ll int i=0;i<n;i++){ans=max(ans,arr[i]*(n-i));}
	cout<<ans<<'\n';
	return 0;
}

1 Like