Maximum Subarray Sum Problem Statement

Given an array of numbers, the task is to find the maximum sum of any contiguous subarray of the array.

Input:

The first line of input contains the size of the array, denoted by N. The second line contains N space-separated integers representing the array elements.

Output:

The first and only line of output should print the maximum subarray sum.

Example:

Input:

6
34 -50 42 14 -5 86

Output:

137

Explanation:

The maximum sum is 137, achieved by summing the subarray [42, 14, -5, 86].

Input:

4
-5 -1 -8 -9

Output:

-1

Explanation:

The maximum sum is -1, which is just the largest number in this case.

Constraints:

The solution should be implemented in O(N) time.

N can be large, so efficient solutions are favorable.

Note:

Consider edge cases such as all numbers being negative.

Question

Maximum Subarray Sum Problem Statement

Given an array of numbers, the task is to find the maximum sum of any contiguous subarray of the array.

Input:

The first line of input contains the size of the array, denoted by N. The second line contains N space-separated integers representing the array elements.

Output:

The first and only line of output should print the maximum subarray sum.

Example:

Input:

6
34 -50 42 14 -5 86

Output:

Explanation:

The maximum sum is 137, achieved by summing the subarray [42, 14, -5, 86].

Input:

4
-5 -1 -8 -9

Output:

-1

Explanation:

The maximum sum is -1, which is just the largest number in this case.

Constraints:

The solution should be implemented in O(N) time.
N can be large, so efficient solutions are favorable.

Note:

Consider edge cases such as all numbers being negative.

Accepted Answer

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

Use Kadane's algorithm to find the maximum subarray sum in O(N) time.
Initialize two variables: max_sum and current_sum to keep track of the maximum sum found so far and the current sum of the subarray being considered.
Iterate through the array and update current_sum by adding the current element or starting a new subarray if the current element is greater than the sum so far.
Update max_sum if current_sum becomes greater than max_sum.
Return max_sum as the maximum subarray sum.
Example: For input [34, -50, 42, 14, -5, 86], the maximum subarray sum is 137.
Example: For input [-5, -1, -8, -9], the maximum subarray sum is -1.

Maximum Subarray Sum Problem Statement

Input:

Output:

Example:

Input:

Output:

Explanation:

Input:

Output:

Explanation:

Constraints:

Note:

Cult.fit Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern