Maximum subarray sum-Coding question asked by Google and Amazon
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.
Maximum possible sum of elements in subarrays.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]Output: 6Explanation: [4,-1,2,1] has the largest sum = 6.
Input: nums = Output: 1
Input: nums = [5,4,-1,7,8]Output: 23
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.