How do I optimize this piece of C++ code?

Question

This has a time limit of one second. My program takes 1.01s for some unknown test cases. The problem is

You are developing a smartphone app. You have a list of potential customers for your app. Each customer has a budget and will buy the app at your declared price if and only if the price is less than or equal to the customer's budget.

You want to fix a price so that the revenue you earn from the app is maximized. Find this maximum possible revenue.

For instance, suppose you have 4 potential customers and their budgets are 30, 20, 53 and 14. In this case, the maximum revenue you can get is 60.

I'm sure that the code is correct. I just want to optimize it. Please help me do so. I'm a beginner.

Code:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int n, x, i, j, k;
    cin >> n;
    vector<int> v;
    for (i = 0; i < n; ++i) 
    {
        cin >> x;
        v.push_back(x);
    }
    int maximum = *max_element(v.begin(), v.end());
    int minimum = *min_element(v.begin(), v.end());
    vector<long long int> sums;
    for (j = minimum; j <= maximum; ++j)
    {
        vector<int> prices;
        for (k = 0; k < n; ++k)
        {
            if (j > v[k]) {
                ;
            } else {
                prices.push_back(j);
            }
        }
        sums.push_back(accumulate(prices.begin(), prices.end(), 0));
        prices.clear();
    }
    long long int maxsum = *max_element(sums.begin(), sums.end());
    cout << maxsum;
}

Answer 1

Here's an example that CodeChef timed at 0.19 s.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  int number;
  std::vector<int> budgets;

  std::cin >> number;

  budgets.resize(number);

  for (std::size_t i = 0; i < budgets.size(); ++i) {
    std::cin >> budgets[i];
  }

  std::sort(budgets.begin(), budgets.end());

  std::size_t max = 0;
  for (std::size_t i = 0; i < budgets.size(); ++i) {
    std::size_t tmp = budgets[i] * (budgets.size() - i);
    if (tmp > max) {
      max = tmp;
    }
  }

  std::cout << max;
}

Once I know the size needed for the vector, I resize it. This stops the vector resizing at element 2, 4, 8, etc. One resize is faster than >1. Now, because it's been resized, I can also just use direct element access with []. .at() is safer but brings exceptions into play, and this exercise is about minimizing runtime, so we won't do it.

The key here is sorting the vector. It's explained in a comment, but the general idea is that sorted data is much faster to work with than un-sorted data. The sort itself runs in O(nlogn) time, but we now get a much faster algorithm.

The new algorithm is relying on sorted data. Index 0 holds the smallest price, which means everyone could afford it at that price. My revenue would be element 0's budget times the number of elements (.size()). When I get to the second element, everyone except index zero can afford it, so my revenue is element 1's budget times the size minus one. And so on. As I calculate these potential revenues, I compare them against my max variable. If I calculate bigger, I replace max with the new value, otherwise I leave it alone.

You'll note that I don't know what price to actually set it at. It wasn't a requirement of the submission, so I don't care.

Personal opinion time, sites like this are terrible for learning. You're better off finding a youtube series or taking a course or getting a good book. These sorts of code golf exercises can be fun, but they do nothing to teach best practices or even what you're doing. They're usually just a test of pattern-finding (which can be beneficial) and rote memorization of certain algorithms (less great).