Loop Array Hash Map Counting Prefix Sum
Intermediate Level

Implement the maximumSubarraySum method that returns the largest sum of any contiguous subarray.

The input contains an integer array nums and its length size. Your task is to find the maximum possible sum of a contiguous subarray.

A contiguous subarray must use consecutive elements from the original array. For example, in [-2,1,-3,4,-1,2,1,-5,4], the best subarray is [4,-1,2,1], whose sum is 6.

Example 1
Input:
nums (int[]) = [-2,1,-3,4,-1,2,1,-5,4]
size (int) = 9
Return:
(int) 6
Example 2
Input:
nums (int[]) = [1]
size (int) = 1
Return:
(int) 1
Example 3
Input:
nums (int[]) = [5,4,-1,7,8]
size (int) = 5
Return:
(int) 23

Use Kadane's algorithm to decide whether to extend the current subarray or start a new one.

At each element, the best subarray ending at that position is either the current element alone or the current element added to the previous running sum.

Keep another variable for the best sum found anywhere in the array.

Pseudocode:

function maximumSubarraySum(nums, size):
    currentSum = nums[0]
    bestSum = nums[0]
    for i from 1 to size - 1:
        currentSum = max(nums[i], currentSum + nums[i])
        bestSum = max(bestSum, currentSum)
    return bestSum
Run your code to see the result.