Hi!
You might have seen problems where you're tasked to find something along the lines of "choosing some subsets that maximize the sum of something". In this post, I'll be discussing some ideas that solve those type of problems. As I'm not sure of a formal definition, I'll call this the Subset Assignment Problem.
P1
You're given an array $$$a$$$ ($$$1\leq a_i\leq 10^9$$$) of size $$$n$$$ ($$$1\leq n\leq 10^5$$$). Find a subset of size $$$k$$$ ($$$0\leq k\leq n$$$) that maximizes the sum.
P2
You're given two arrays $$$a$$$ and $$$b$$$ ($$$1\leq a_i, b_i\leq 10^9$$$), both of size $$$n$$$ ($$$1\leq n\leq 10^5$$$). Find two disjoint subsets $$$S$$$ and $$$T$$$ of sizes $$$k_1$$$ an $$$k_2$$$ ($$$0\leq k_1, k_2\leq n$$$, $$$k_1 + k_2 = n$$$) respectively that maximizes $$$\sum_{i\in S}a_i + \sum_{i\in T}b_i$$$.
P3: CSES Programmers and Artists
You're given two arrays $$$a$$$ and $$$b$$$ ($$$1\leq a_i, b_i\leq 10^9$$$), both of size $$$n$$$ ($$$1\leq n\leq 10^5$$$). Find two disjoint subsets $$$S$$$ and $$$T$$$ of sizes $$$k_1$$$ an $$$k_2$$$ ($$$0\leq k_1, k_2\leq n$$$) respectively that maximizes $$$\sum_{i\in S}a_i + \sum_{i\in T}b_i$$$.
Now let's take a look at some non-standard problems.
P4: 1799F - Halve or Subtract
P5: JOI 2022 Let's Win the Election
Hope you all found this helpful!