Max Contiguous Subarray (Kadane's) [Medium (just cause its tricky)]

https://leetcode.com/problems/maximum-subarray/

Find the contiguous (meaning elems must be one right after the other) subarray whose sum is max possible in the given array

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

def mcsa(A: Array[Int]) = {

    @tailrec
    def go(i: Int, maxSoFar: Int, currMax: Int): Int = {
      if (i < A.length) {
        val nextCurrMax = Math.max(0, currMax + A(i))
        go(
          i + 1,
          if (nextCurrMax > 0) Math.max(nextCurrMax, maxSoFar)
          else if (A(i) > maxSoFar) A(i)
          else maxSoFar,
          nextCurrMax
        )
      } else maxSoFar
    }

    go(1, A(0), A(0))
}