Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize $$ \left(\sum_{i \in S} a_i\right)\left(\sum_{i \notin S} b_i\right) $$
A naive solution is to iterate over the powerset of $\{1, 2, \dots ,n\}$ and find the maximum value, which is $O(n2^n)$. How to use dynamic programming to solve this?
Any comments would be appreciated.
If you could solve this problem, then you would be able to solve the NP-complete PARTITION problem. The partition problem asks whether a given set of positive integers $X$ can be partitioned into two equal parts. Given a set $X$ whose sum is $M$, choose an arbitrary ordering of its elements $X = \{x_1,\ldots,x_n\}$, and let $A=B=X$. Your problem asks to maximize $$ f(S) = \left(\sum_{i \in S} x_i \right) \left(M - \sum_{i \in S} x_i\right). $$ As a quadratic in $\sigma = \sum_{i \in S} x_i$, $f(S)$ is maximized at $\sigma = M/2$, at which we have $f = (M/2)^2$. This is achievable for some set $S$ iff $X$ can be partitioned into two equal halves.
