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

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

}