The largest-sum subarray

def max_subarray(nums):
    best = end = nums[0]                # end: best sum of a subarray ending here
    for x in nums[1:]:
        end = max(end + x, x)           # extend, or restart at x
        best = max(best, end)
    return best

#include <algorithm>
#include <vector>

long long solve(const std::vector<int>& nums) {
    long long best = nums[0], end = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        end = std::max(end + nums[i], (long long)nums[i]);   // extend or restart
        best = std::max(best, end);
    }
    return best;
}

class Solution {
    public long maxSubarray(int[] nums) {
        long best = nums[0], end = nums[0];
        for (int i = 1; i < nums.length; i++) {
            end = Math.max(end + nums[i], nums[i]);   // extend or restart
            best = Math.max(best, end);
        }
        return best;
    }
}

function maxSubarray(nums) {
  let best = nums[0], end = nums[0];
  for (let i = 1; i < nums.length; i++) {
    end = Math.max(end + nums[i], nums[i]);   // extend or restart
    best = Math.max(best, end);
  }
  return best;
}

fn solve(nums: &[i64]) -> i64 {
    let (mut best, mut end) = (nums[0], nums[0]);
    for &x in &nums[1..] {
        end = (end + x).max(x);                       // extend or restart
        best = best.max(end);
    }
    best
}

solve :: [Int] -> Int
solve (x : xs) = fst (foldl step (x, x) xs)
  where
    -- (best so far, best ending here)
    step (best, end) y = let end' = max (end + y) y in (max best end', end')
solve [] = 0