Description:
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Examples:
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.Solution in Python:
To solve the problem of finding the subarray with the largest sum, we can use Kadane’s Algorithm. This algorithm efficiently finds the maximum sum of a contiguous subarray in O(n) time.
Python
from typing import List
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# Initialize the variables to store the maximum sum found so far and the current sum
max_sum = float('-inf')
current_sum = 0
# Iterate over each number in the array
for num in nums:
# Update the current sum by including the current number
current_sum += num
# Update the maximum sum found so far if the current sum is greater
if current_sum > max_sum:
max_sum = current_sum
# If the current sum drops below zero, reset it to zero
if current_sum < 0:
current_sum = 0
return max_sumExplanation:
- Initialization:
max_sumis initialized to negative infinity (float('-inf')) to ensure that any sum we encounter will be larger.current_sumis initialized to 0 to start calculating the sum of subarrays from the beginning.
- Iterating Through the Array:
- For each number in the array (
for num in nums), we add the number tocurrent_sum. - If
current_sumexceedsmax_sum, we updatemax_sumto becurrent_sum.
- For each number in the array (
- Resetting the Current Sum:
- If
current_sumdrops below 0, it means that the current subarray cannot contribute positively to any future subarray sum, so we resetcurrent_sumto 0.
- If
- Returning the Result:
- After iterating through the array,
max_sumwill hold the maximum sum of any contiguous subarray, which we return.
- After iterating through the array,
Kadane’s Algorithm:
- Time Complexity: O(n), where n is the length of the input array. This is because we only pass through the array once.
- Space Complexity: O(1), as we use a constant amount of extra space regardless of the input size.
This solution effectively finds the maximum subarray sum in a single pass through the array, making it optimal for large input sizes as specified in the problem constraints.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
// Initialize variables to store the maximum sum found so far and the current sum
let maxSum = Number.NEGATIVE_INFINITY;
let currentSum = 0;
// Iterate through each number in the array
for (let num of nums) {
// Update the current sum by including the current number
currentSum += num;
// Update the maximum sum found so far if the current sum is greater
if (currentSum > maxSum) {
maxSum = currentSum;
}
// If the current sum drops below zero, reset it to zero
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
};Solution in Java:
Java
class Solution {
public int maxSubArray(int[] nums) {
// Initialize variables to store the maximum sum found so far and the current sum
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
// Iterate through each number in the array
for (int num : nums) {
// Update the current sum by including the current number
currentSum += num;
// Update the maximum sum found so far if the current sum is greater
maxSum = Math.max(maxSum, currentSum);
// If the current sum drops below zero, reset it to zero
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
}
}Solution in C#:
C#
public class Solution {
public int MaxSubArray(int[] nums) {
// Initialize variables to store the maximum sum found so far and the current sum
int maxSum = int.MinValue;
int currentSum = 0;
// Iterate through each number in the array
foreach (int num in nums) {
// Update the current sum by including the current number
currentSum += num;
// Update the maximum sum found so far if the current sum is greater
maxSum = Math.Max(maxSum, currentSum);
// If the current sum drops below zero, reset it to zero
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
}
}