Random Wits

Life is too short for a diary

$ about
├── tags

├── bookshelf

├── resources

├── quotes

├── habits

└── bio







Sun 12 Sep 2021

Maximum Subarray

Tags: programming leetcode code dp

There's an interesting problem I recently solved on leetcode based on dynamic programming. My Github repository contains list of all problems that I have solved.

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.1

Brute force algorithm

We can commence with a brute force algorithm. For every element of array, we compare its sum with the rest of the element to calculate maximum sum.

img

class Solution {
    public int maxSubArray(int[] nums) {
        
        if (nums.length == 1){
            return nums[0];
        }

        int output = nums[0];
        
        for (int i = 0; i < nums.length; i++) {
            int tempSum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                tempSum += nums[j];
                output = Math.max(tempSum, output);
            }
            
            output = Math.max(output, nums[i]);
            
        }     
        return output;   
        
    }
}

Time complexity is O(n2) and the execution time is 110 ms on leetcode.

More efficient solution

We can use Kadane algorithm to solve. It cans the given array A[1..n] from left to right. In the jth step, it computes the subarray with the largest sum ending at j; this sum is maintained in variable cSum. It computes the subarray with the largest sum anywhere in A[1..j], maintained in variable oSum;

class Solution {
    public int maxSubArray(int[] nums) {
        
        if (nums.length == 1){
            return nums[0];
        }

        int cSum = nums[0];
        int oSum = nums[0];
        
        for (int i = 1; i < nums.length; i++){
            if (nums[i] > nums[i] + cSum) {
                cSum = nums[i];
                
            } else { 
                cSum += nums[i];
            }
            oSum = Math.max(oSum, cSum);
        }
 
        return oSum;
  
    }
}

The time complexity is O(n). The execution time took 0 ms on leetcode.


comments powered by Disqus