Maximum Sum Subarray Problem Statement

Given an array of integers, find the maximum sum of any contiguous subarray within the array.

Example:

Input:

array = [34, -50, 42, 14, -5, 86]

Output:

137

Explanation:

The maximum sum of a contiguous subarray is 137, which is the sum of the elements [42, 14, -5, 86].

Input:

array = [-5, -1, -8, -9]

Output:

-1

Explanation:

The maximum sum of a contiguous subarray is -1, as choosing any subarray cannot yield a greater sum.

Input:

N
array of N space-separated integers

Output:

Maximum sum of any contiguous subarray

Constraints:

1 ≤ N ≤ 10⁵

-10⁴ ≤ array[i] ≤ 10⁴

Note:

The solution should be accomplished in O(N) time complexity.

Question

Maximum Sum Subarray Problem Statement

Given an array of integers, find the maximum sum of any contiguous subarray within the array.

Example:

Input:

array = [34, -50, 42, 14, -5, 86]

Output:

Explanation:

The maximum sum of a contiguous subarray is 137, which is the sum of the elements [42, 14, -5, 86].

Input:

array = [-5, -1, -8, -9]

Output:

-1

Explanation:

The maximum sum of a contiguous subarray is -1, as choosing any subarray cannot yield a greater sum.

Input:

N
array of N space-separated integers

Output:

Maximum sum of any contiguous subarray

Constraints:

1 ≤ N ≤ 10⁵
-10⁴ ≤ array[i] ≤ 10⁴

Note:

The solution should be accomplished in O(N) time complexity.

Accepted Answer

Find the maximum sum of any contiguous subarray within an array in O(N) time complexity.

Use Kadane's algorithm to find the maximum sum subarray in O(N) time complexity
Initialize two variables: max_sum and current_sum to keep track of the maximum sum subarray
Iterate through the array and update current_sum by adding the current element or starting a new subarray
Update max_sum if current_sum is greater than max_sum
Return max_sum as the maximum sum of any contiguous subarray

Accepted Answer

import java.util.Scanner;

public class MaximumSumSubarray {

public static int maxSubArraySum(int[] nums) {

int maxSum = nums[0]; // Initialize maxSum with the first element of the array

int currentSum = nums[0]; // Initialize currentSum with the first element of the array

for (int i = 1; i < nums.length; i++) {

// Compare currentSum + nums[i] with nums[i]

// If currentSum + nums[i] is greater, update currentSum, else start a new subarray

currentSum = Math.max(nums[i], currentSum + nums[i]);

// Update maxSum if currentSum is greater

maxSum = Math.max(maxSum, currentSum);

}

return maxSum;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int N = sc.nextInt(); // Size of the array

int[] nums = new int[N];

for (int i = 0; i < N; i++) {

nums[i] = sc.nextInt(); // Read the array elements

}

int result = maxSubArraySum(nums);

System.out.println(result); // Print the maximum subarray sum

}

Asked in ThoughtWorks