Maximum subarray sum-Coding question asked by Google and Amazon

Problem Statement:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Input format:

Array

Output format:

Maximum possible sum of elements in subarrays.

.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Approach 1-Iterating along the array:

We iterate along the array and create another vector array to push the elements into it & formed desired subarray. The subarray returning highest sum, returns the final answer.

Time complexity: O(n²)

Code for approach 1:

Approach 2-Kadane’s algorithm:

The algorithm works on the sense that instead of finding each possible sub-array, we may iterate through the array once and find the maximum possible sum. To do so, we will keep on adding value of each element to a declared variable. It will be turned zero if sum turns out be negative.

This works on the basis that sub-arrays are contiguos as well as each element is part of a sub-array.

Code for Approach-2:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning