Amazon Interview Questions: Maximum Subarray Sum Given an array of numbers, find the max

Asked inAmazon,Software Developer

Maximum Subarray Sum

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

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

Input Format:

The first line of input contains size of array, which is denoted by N and second line of input contains N space separated integers.

Output Format:

The first and only line of output should print the maximum subarray sum, as described in the description.

Prajkta Shendge

13d

student at

Savitribai phule Pune University

-1

Akshay Rajput

15d

To solve this problem in time, we can use Kadane's Algorithm. This algorithm efficiently computes the maximum sum of a contiguous subarray in linear time. Here's the step-by-step solution: Algorithm 1...read more

supremetoad

22d

ex -

TCS

Test

maryam kasadisss

3mo

Approach Create a nested loop. The outer loop will go from i = 0 to i = n - k. This will cover the starting indices of all k-subarrays The inner loop will go from j = i to j = i + k - 1. This will cov...read more

Anonymous

4mo

fulfillingsole

4mo

student at

Asian University Manipur msc complete

fashionableoggy

5mo

works at

FPL Hyundai Ambattur

-1

sunnyflamingo

5mo

student at

RvNorth land higher education and traning

Md Imam

5mo

B.A complete

Preeti Margaret Bhengra

5mo

-1

Anonymous

5mo

UREVENUKA SHIVAJI

5mo

-1

Bukke Seva naik

6mo

student at

JNTU College of Engineering, Kakinada

-1

༒ SINGH༒

6mo

student at

Gems polytechnic college

-1

K sai swathi

6mo

-1

tremendoussage

6mo

student at

Baahubali College of Engineering

-1

Rajeswari NANDAVARAPU

6mo

-1

Rajeswari NANDAVARAPU

6mo

-1

endlesstaro

7mo

ex -

HTC Global Services

-1

avinash verma

7mo

-1

Anonymous

7mo

-1

Anonymous

7mo

-1

Dayakar Behra

7mo

To solve the problem of finding the maximum sum of any contiguous subarray of an array in O(N) time, we can use Kadane's Algorithm. This algorithm works by iterating through the array and at each step...read more

Vaishali

8mo

-1

Shaik Naseema

11mo

ARR1(34690)

Shaik Naseema

11mo

Shaik Naseema

11mo

N-(1) is smallest number

Shaik Naseema

11mo

N-(1) is smallest

Anonymous

-1

Anonymous

The maximum sum would be -1

chandankumar6301

currently not working

The maximum sum would be -1

chandankumar6301

currently not working

import java.util.Scanner; public class MaximumSubarraySum { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // Input size of array int N = scanner.nextInt(); // Inpu...read more

Anonymous

The maximum sum would be -1

Anonymous

The maximum sum would be -1

Sweet Swathi

the maximum sum would be -1.

Anonymous

Send line elements is maximum sum is -1

Ruchi Gupta

Time Complexity - O(N * K)

Space Complexity - O(1)

where N is the length of the array and K is the size of subarrays

void printSubarrayMax(int *arr, int n, int k)

{

if (n == 0 || k == 0)

{

return;

Add answer anonymously...

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

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

Input Format:

The first line of input contains size of array, which is denoted by N and second line of input contains N space separated integers.

Output Format:

The first and only line of output should print the maximum subarray sum, as described in the description.

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer