Largest Subarray Google OA Solution

Largest Subarray Google OA Solution

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

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_sum

Program: 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 result

The 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 result

Complexity 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;
    }
};

Google Online Assessment 2022

Related:

Leave a Comment

three × 3 =