Remove entries from array to sort it and maximize sum of elements
Haskell, \$O(n \log n)\$ time, \$O(n)\$ space

{-# LANGUAGE MultiParamTypeClasses #-}

import qualified Data.FingerTree as F

data S = S
  { sSum :: Int
  , sArr :: [Int]
  } deriving (Show)

instance Monoid S where
  mempty = S 0 []
  mappend _ s = s

instance F.Measured S S where
  measure = id

bestSubarrays :: [Int] -&gt; F.FingerTree S S
bestSubarrays [] = F.empty
bestSubarrays (x:xs) = left F.&gt;&lt; sNew F.&lt;| right'
  where
    (left, right) = F.split (\s -&gt; sArr s &gt; [x]) (bestSubarrays xs)
    sLeft = F.measure left
    sNew = S (x + sSum sLeft) (x : sArr sLeft)
    right' = F.dropUntil (\s -&gt; sSum s &gt; sSum sNew) right

bestSubarray :: [Int] -&gt; [Int]
bestSubarray = sArr . F.measure . bestSubarrays


How it works

bestSubarrays xs is the sequence of subarrays of xs that are on the efficient frontier of {largest sum, smallest first element}, ordered from left to right by increasing sum and increasing first element.

To go from bestSubarrays xs to bestSubarrays (x:xs), we


split the sequence into a left side with first elements less than x, and a right side with first elements greater than x,
find a new subarray by prepending x to the rightmost subarray on the left side,
drop the prefix of subarrays from the right side with smaller sum than the new subarray,
concatenate the left side, the new subarray, and the remainder of the right side.


A finger tree supports all these operations in \$O(\log n)\$ time.