Contents
Largest Subarray Google OA 2023 Solution
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.
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 <= 105-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
SOLUTION
Program: Largest Subarray Google OA Solution in Python
At each index, keep track of the maximum sum using DP table , till that point
- Save the maximum between [cur_value, max_so_far+cur_value]
- Finally, return the maximum out of the table
time O(n)
space O(n)
def maxSubArray(self, nums):
dp = [0]*len(nums)
for i,num in enumerate(nums):
dp[i] = max(dp[i-1] + num, num)
return max(dp)To save space, implementation without using DP table
At each index, keep track of the maximum sum using variable (max_sum_until_i, and max_sum_sofar)
- max_until_i = max (max_until_i, max_until_i+cur_value)
- max_sum_sofar = max(max_until_i, max_sum_sofar,cur_value)
- Finally, return the max_sum_sofar
time O(n)
space O(1)
def maxSubArray(self, nums):
max_sum_until_i = max_sum= nums[0]
for i, num in enumerate(nums[1:],start=1):
max_sum_until_i = max(max_sum_until_i+num, num)
max_sum = max(max_sum,max_sum_until_i,max_sum)
return max_sumProgram: Largest Subarray Google OA Solution in Python
Idea:
- Suppose there is a max sum of a subarray starting from position i+1 (we can call it val[i+1]). At position i, we want to get the max sum of subarray starting from i, the top-down question will be: Should we add val[i+1] to nums[i]?
val[i] = max(nums[i], nums[i] + val[i+1])
#Where val[i] is the max sum of the subarray that starts from i (must include nums[i])
Steps:
- By traversing the whole nums array in a reversed order, we get the val array which contain the result somewhere in it.
Code:
In my code, because once I traverse an element in the nums, I won’t reuse that element anymore, therefore I don’t have to create the “val” array, instead I just set the “val” value to the existing nums array, just for memory saving.
INF = -10**5
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(len(nums)-2, -1, -1):
nums[i] = max(nums[i], nums[i] + nums[i+1])
result = INF
for i in range(len(nums)):
result = max(result, nums[i])
return resultThe above code is to let you understand the idea thoroughly, another compressed solution (with same idea) will be:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
result = nums[-1]
for i in range(len(nums)-2, -1, -1):
nums[i] = max(nums[i], nums[i] + nums[i+1])
result = max(result, nums[i])
return resultComplexity Analysis:
- Time complexity: O(2n) -> O(n)
- Space complexity: O(1) – (Because I didn’t initiate any array)
Divide and Conquer Approch
Split our array into two halves
case1: maxSum subaaray occur in left half ,
case2: maxSum subarray occur in right half
case3: maxSum subaaray lies about middle of array
We use here divide and conquer approch here , split array into two halves about middle
take anwer from left , right , and subArray about middle.
Let assume recusion will give us answer for left and right part , how do we calculate maxsum subarray about mid :
[-2,1,-3,4,-1,2,1,-5,4]
i = 0 , j = 8
mid = (0+8)/2 = 4
step 1) Caluate maxSum (maximum positive sum) from mid to left
int sum = 0,leftMaxSUM = Integer.MIN_VALUE;
for(int l = mid;l>=i;l--){
sum+=nums[l];
if(sum>leftMaxSUM ){
leftMaxSUM = sum;
}
}step 2) calculate maxSum(maximum positive sum ) from mid+1 to right side
int rightMaxSUM = Integer.MIN_VALUE;
sum = 0; // reset sum to 0
for (int l = mid + 1; l <=j; l++)
{
sum += nums[l];
if (sum > rightMaxSUM ) {
rightMaxSUM = sum;
}
}int midSum = leftMaxSUM+rightMaxSUM
Program: Largest Subarray Google OA Solution
public int maxSubArray(int[] nums) {
return helper(nums,0,nums.length-1);
}
public int helper(int nums[],int i,int j){
if(i==j){
return nums[i];
}
int mid = (i+j)/2;
int sum = 0,leftMaxSUM = Integer.MIN_VALUE;
for(int l = mid;l>=i;l--){
sum+=nums[l];
if(sum>leftMaxSUM){
leftMaxSUM = sum;
}
}
int rightMaxSUM = Integer.MIN_VALUE;
sum = 0; // reset sum to 0
for (int l = mid + 1; l <=j; l++)
{
sum += nums[l];
if (sum > rightMaxSUM ) {
rightMaxSUM = sum;
}
}
int maxLeftRight = Math.max(helper(nums, i, mid),
helper(nums, mid + 1, j ));
return Math.max(maxLeftRight, leftMaxSUM + rightMaxSUM );
}Kadane’s algorithm
Program: Largest Subarray Google OA Solution in C++
The idea of Kadane’s algorithm is to look for all positive contiguous segments of the array (maxendinghere is used for this). And keep track of maximum sum contiguous segment among all positive segments (maxsofar is used for this). Each time we get a positive-sum compare it with maxsofar and update maxsofar if it is greater than maxsofar .
Initialize:
max_so_far = INT_MIN
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_far
CODE With Kadane’s Algorithm :
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sum=INT_MIN, curr_sum=0;
for(int i=0;i<nums.size();i++){
curr_sum+=nums[i];
if(curr_sum>max_sum)
max_sum=curr_sum;
if(curr_sum<0)
curr_sum=0;
}
return max_sum;
}
};CODE With 0ms time :
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int cs=nums[0], ms=nums[0];
for(int i=1; i<nums.size();i++)
{
cs = max(nums[i], cs+nums[i]);
ms=max(cs, ms);
}
return ms;
}
};Related:
- Amazon OA Online Assessment 2022 Questions and Answers
- Microsoft Online Assessment 2021 Questions and Solution
- Google Online Assessment 2022 Questions
