Sponsored
Sponsored
First, pair up each player's score and age, and then sort them based on age and score. This allows us to always build teams that do not violate the conflict rule of younger players having higher scores than older players. Subsequently, use dynamic programming to build the optimal solution progressively by calculating the best team score achievable up to this player, considering current player's score only if it resolves no conflicts by adhering to the sorted order.
Time Complexity: O(n^2), where n is the number of players.
Space Complexity: O(n) for the DP array.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void* a, const void* b) {
5 int* x = (int*)a;
6 int* y = (int*)b;
7 return (x[0] == y[0]) ? (x[1] - y[1]) : (x[0] - y[0]);
8}
9
10int bestTeamScore(int* scores, int scoresSize, int* ages) {
11 int players[scoresSize][2];
12 for (int i = 0; i < scoresSize; ++i) {
13 players[i][0] = ages[i];
14 players[i][1] = scores[i];
15 }
16 qsort(players, scoresSize, sizeof(players[0]), compare);
17
18 int dp[scoresSize];
19 int maxScore = 0;
20 for (int i = 0; i < scoresSize; ++i) {
21 dp[i] = players[i][1];
22 for (int j = 0; j < i; ++j) {
23 if (players[j][1] <= players[i][1]) {
24 if (dp[j] + players[i][1] > dp[i]) {
25 dp[i] = dp[j] + players[i][1];
26 }
27 }
28 }
29 if (dp[i] > maxScore) {
30 maxScore = dp[i];
31 }
32 }
33 return maxScore;
34}Sorts player data in a two-dimensional array in C, then applies DP to achieve the highest possible team score ignoring conflicts using sorted order.