Algorithm (DP)

• Let $f(i)$ denote the max subarray sum with the underlying subarray ending at arr[i].
• Then we have that $f(i) = A[i]$ if $i = 0$ and $f(i) = \max\{f(i - 1) + A[i], A[i]\}$ otherwise.
• The desired answer is then $\max_{0,…,N - 1} f(i)$.

Code

 class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    auto f = rec([&, memo = vector<optional<int>>(size(nums), optional<int>{})](auto&& f, int i) mutable -> int {
      if (memo[i])
        return *memo[i];
      else
        return *(memo[i] = [&]{
          if (i == 0)
            return nums[i];
          else
            return std::max(nums[i], f(i - 1) + nums[i]) 
        }());
    });

    const auto solution = [&](int acc = INT_MIN) {
      for (int i = 0; i < size(nums); ++i)
        acc = std::max(acc, f(i));
      return acc;
    }();

    return solution;
  }
};