Maximum Subarray

                                            
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for(int i = 1; i < nums.size(); i++){
            currentSum = max(nums[i], currentSum + nums[i]);
            maxSum = max(maxSum, currentSum);
        }
        
        return maxSum;
    }
};

                                            
class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

                                            
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_sum = nums[0]
        current_sum = nums[0]
        
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            max_sum = max(max_sum, current_sum)
            
        return max_sum

                                            
int maxSubArray(int* nums, int numsSize) {
    int max_sum = nums[0];
    int current_sum = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        current_sum = (current_sum + nums[i] > nums[i]) ? current_sum + nums[i] : nums[i];
        max_sum = (current_sum > max_sum) ? current_sum : max_sum;
    }
    
    return max_sum;
}

                                            
public class Solution {
    public int MaxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            currentSum = Math.Max(nums[i], currentSum + nums[i]);
            maxSum = Math.Max(maxSum, currentSum);
        }

        return maxSum;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if (nums.length === 1) return nums[0];
    
    let maxSum = nums[0];
    let currentSum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};

                                            
function maxSubArray(nums: number[]): number {
    let currentSum = nums[0];
    let maxSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxSubArray($nums) {
        $maxSum = $nums[0];
        $tempSum = $nums[0];
        
        for ($i = 1; $i < count($nums); $i++) {
            $tempSum = max($nums[$i], $tempSum + $nums[$i]);
            $maxSum = max($maxSum, $tempSum);
        }
        
        return $maxSum;
    }
}

                                            
class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var maxSum = nums[0]
        var currentSum = nums[0]
        
        for i in 1..<nums.count {
            currentSum = max(nums[i], currentSum + nums[i])
            maxSum = max(maxSum, currentSum)
        }
        
        return maxSum
    }
}

                                            
class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var maxSum = nums[0]
        var currentSum = nums[0]
        
        for (i in 1 until nums.size) {
            currentSum = maxOf(nums[i], currentSum + nums[i])
            maxSum = maxOf(maxSum, currentSum)
        }
        
        return maxSum
    }
}

                                            
class Solution {
  int maxSubArray(List<int> nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
      currentSum = nums[i] + (currentSum > 0 ? currentSum : 0);
      if (currentSum > maxSum) {
        maxSum = currentSum;
      }
    }
    
    return maxSum;
  }
}

                                            
func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    maxSum := nums[0]
    currentSum := nums[0]
    
    for i := 1; i < len(nums); i++ {
        currentSum = max(nums[i], currentSum+nums[i])
        maxSum = max(maxSum, currentSum)
    }
    
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def max_sub_array(nums)
    max_sum = nums[0]
    current_sum = nums[0]
    
    (1..nums.length - 1).each do |i|
        current_sum = [nums[i], current_sum + nums[i]].max
        max_sum = [max_sum, current_sum].max
    end
    
    max_sum
end

                                            
object Solution {
    def maxSubArray(nums: Array[Int]): Int = {
        var maxSum = nums(0)
        var currentSum = nums(0)
        
        for (i <- 1 until nums.length) {
            currentSum = Math.max(nums(i), currentSum + nums(i))
            maxSum = Math.max(maxSum, currentSum)
        }
        
        maxSum
    }
}

                                            
impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut max_sum = nums[0];
        let mut current_sum = nums[0];

        for i in 1..nums.len() {
            current_sum = current_sum.max(0) + nums[i];
            max_sum = max_sum.max(current_sum);
        }

        max_sum
    }
}

                                            
(define/contract (max-sub-array nums)
  (-> (listof exact-integer?) exact-integer?)
  
  (let loop ([max-sum (car nums)]
             [current-sum (car nums)]
             [rest (cdr nums)])
    (cond
      [(null? rest) max-sum]
      [(< (car rest) (+ current-sum (car rest)))
       (loop (max max-sum (+ current-sum (car rest)))
             (+ current-sum (car rest))
             (cdr rest))]
      [else
       (loop (max max-sum (car rest))
             (car rest)
             (cdr rest))])))

                                            
-spec max_sub_array(Nums :: [integer()]) -> integer().
max_sub_array(Nums) ->
    {_, _, Max} = lists:foldl(fun(X, {SoFar, EndHere, Max}) ->
                                  NewSoFar = max(X, SoFar + X),
                                  NewEndHere = max(NewSoFar, EndHere),
                                  NewMax = max(Max, NewEndHere),
                                  {NewSoFar, NewEndHere, NewMax}
                              end, {-9999999, -9999999, -9999999}, Nums),
    Max.

                                            
defmodule Solution do
  @spec max_sub_array(nums :: [integer]) :: integer
  def max_sub_array(nums) do
    {_, max_sum} = Enum.reduce(tl(nums), {hd(nums), hd(nums)}, fn num, {current_sum, max_sum} ->
      current_sum = max(num, current_sum + num)
      max_sum = max(current_sum, max_sum)

      {current_sum, max_sum}
    end)

    max_sum
  end
end

To solve this coding challenge, we will use Kadane's Algorithm, which is an efficient way to find the maximum sum subarray with a time complexity of O(n). Below, I present the methodology in detail, including explanations and pseudocode.

# Explanation

This challenge asks us to find the maximum sum of a subarray from the given array of integers. A subarray is any contiguous part of the array, and the task is to find the one with the highest sum. We will use Kadane's Algorithm, which is renowned for its efficiency in solving this problem with linear time complexity \(O(n)\). Kadane's Algorithm works on the principle of maintaining the maximum subarray sum ending at the current index and updating the result based on this information. It does this by iterating through the array and keeping track of two values:

current_sum

: The sum of the subarray ending at the current position.
max_sum

: The maximum sum encountered so far among all possible subarrays.

The algorithm initializes these two values with the first element of the array. As it traverses the array, at each index, it decides whether to:

Include the current element in the existing subarray (
current_sum + nums[i]

) or
Start a new subarray with the current element (
nums[i]

).

The

max_sum

is updated to be the highest sum found so far. Let's now define the detailed steps in pseudocode.

Detailed Steps in Pseudocode

Initialization :

Start by initializing
max_sum

and
current_sum

with the first element of the array. This ensures that we account for arrays with only one element correctly.

                                            
# Initialize max_sum and current_sum with the first element of the array
max_sum = nums[0]
current_sum = nums[0]

Iterate through the array :

Begin from the second element (index 1) and iterate through the entire array.
At each step, update the
current_sum

to be the maximum of either adding the current element to
current_sum

or the current element itself. This decision is based on comparing the sum of continuing the subarray with starting anew from the current element.
Update
max_sum

to be the maximum value between
max_sum

and
current_sum

.

                                            
# Iterate through the array starting from the second element
for i = 1 to len(nums) - 1:
# Update current_sum to include the current element or reset to current element
current_sum = max(nums[i], current_sum + nums[i])

# Update max_sum if current_sum is greater
max_sum = max(max_sum, current_sum)

Return the result :

Once the iteration is complete, the
max_sum

will hold the maximum subarray sum.

                                            
# Return the maximum subarray sum found
return max_sum

Pseudocode with Comments

                                            
# Initialize the necessary variables
max_sum = nums[0]  # This will store the maximum sum of subarrays found
current_sum = nums[0]  # This will store the sum of the current subarray

# Loop through the array starting from the second element
for i = 1 to len(nums) - 1:
    # Determine whether to add the current element to the current subarray
    # or start a new subarray with the current element
    current_sum = max(nums[i], current_sum + nums[i])
    
    # Update the max_sum if the current_sum is greater than max_sum
    max_sum = max(max_sum, current_sum)

# The result is the maximum subarray sum found
return max_sum

By following this approach, you are leveraging Kadane's Algorithm to efficiently find the maximum sum subarray with a linear time complexity. This ensures that the algorithm performs well even with the larger constraints provided.