C++ O(K^2) solution (solved the question 3 minutes after contest : ( )
cpp\ntypedef long long ll;\n\n\nconst ll MAXK = 2e3 + 5;\n\n\nll dp[MAXK];\nll lst[MAXK];\n\nclass Solution {\npublic:\n    \n    long long kSum(vector<int>& nu
```cpp\ntypedef long long ll;\n\n\nconst ll MAXK = 2e3 + 5;\n\n\nll dp[MAXK];\nll lst[MAXK];\n\nclass Solution {\npublic:\n    \n    long long kSum(vector<int>& nums, int k) {\n        ll N = nums.size();\n        memset(dp, 0, sizeof(dp));\n        memset(lst, 0, sizeof(lst));\n        for (auto &i: nums) {\n            dp[1] += max(i, 0);\n            i = abs(i);\n        }\n        sort(nums.begin(), nums.end());\n        \n        for (ll i = 2; i <= k; i ++) {\n            ll chosen = 0, chosenval = -0x3f3f3f3f3f3f3f3f;\n            for (ll j = 1; j < i; j ++) {\n                if (lst[j] < N && chosenval < dp[j] - nums[lst[j]]) {\n                    chosenval = dp[j] - nums[lst[j]];\n                    chosen = j;\n                }\n            }\n            dp[i] = chosenval;\n            lst[chosen] ++;\n            lst[i] = lst[chosen];\n        }\n        \n        return dp[k];\n    }\n};\n```\n\nThe idea is, the x\'s answer could only be the answer by removing an element from all x-1s answer\'s sequence. We maintain a lst[i] to save which element index we are on to remove.\n\nFor the negative value we only add them into removing but not getting dp[1].\n\np.s. I got how to solve on the last 3 minutes of contest, after I written solution, I forgot to add the lst[i] = lst[chosen] row. So I did not pass. \uD83D\uDE2D
['Dynamic Programming']