Given N points in 2D plane, (from 1 to n)
X[ 1…n ]
Y[ 1…n ]
Select K points P_1...P_k to maximize the following value
Value = \sum_{i=1}^{k} (X_i * \sum_{j=1}^{i-1} Y_j)
The K points is a permutation of subset C_{K}^{N}
1 Like
I believe the naive approach would be C_{K}^{N} * P_{K}^{K} * K
I wonder if there is a faster approach?
What was the required complexity?
1 Like
Adding an example
Input: N, K, X[ 1…n ], Y[ 1…n ]
Output: Maximum Value Possible
Example:
N = 4
K = 3
X = [1, 5, 2, 8]
Y = [9, 7, 4, 3]
Maximum Value Possible: 173
Where the points sequence is {1, 9}, {5, 7}, {8, 3}
the Value is 1\times0 \ + \ 5\times9 \ + \ 8\times(9+7) \ = \ 173