- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have two lists called scores and ages, where scores[i] and ages[i] represents the score and age of the ith player in a basketball game. We want to select the team with the highest overall score. Here the score of the team is the total sum of scores of all the players in the team. But we do not allow conflicts in the game. Here a conflict exists if a younger player has a strictly higher score than an older player.

So, if the input is like scores = [5,7,9,14,19], ages = [5,6,7,8,9], then the output will be 54 as we can select all players.

To solve this, we will follow these steps −

- sa := a list of pairs formed by taking elements a and s from ages and scores respectively
- sort the list sa
- scores := make a list of scores from sa
- maxScore := 0
- n := size of scores
- dp := an array of length n and fill with 0
- for i in range 0 to n - 1, do
- score := scores[i]
- dp[i] := score
- for j in range 0 to i - 1, do
- if scores[j] <= score, then
- dp[i] := maximum of dp[i] and dp[j] + score

- if scores[j] <= score, then
- maxScore := maximum of maxScore and dp[i]

- return maxScore

Let us see the following implementation to get better understanding −

def solve(scores, ages): sa = [[a,s] for a,s in zip(ages,scores)] sa.sort() scores = [s for a,s in sa] maxScore = 0 n = len(scores) dp = [0] * n for i in range(n): score = scores[i] dp[i] = score for j in range(i): if scores[j] <= score: dp[i] = max(dp[i],dp[j] + score) maxScore = max(maxScore, dp[i]) return maxScore scores = [5,7,9,14,19] ages = [5,6,7,8,9] print(solve(scores, ages))

[5,7,9,14,19], [5,6,7,8,9]

54

- Related Questions & Answers
- How to Deal With Team Attrition
- Python Program to find whether a no is power of two
- Find K-Length Substrings With No Repeated Characters in Python
- Program to find best position for a service center in Python
- Find memory conflicts among multiple threads in C++
- Python Program to find whether a no is the power of two
- Program to find n length string made of letters from m sized alphabet with no palindrome in Python
- Techniques To Resolve Workplace Conflicts
- Java Program to generate random numbers with no duplicates
- How to handle conflicts in the workplace?
- Program to Find Out the Best Interval to Remove in C++
- Program to find number with thousand separator in Python
- Program to find path with minimum effort in Python
- Program to find tuple with same product in Python
- Program to find largest submatrix with rearrangements in Python

Advertisements