Sun 12 Sep 2021

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}

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.

Time complexity is **O(n ^{2})** and the execution time is 110 ms on leetcode.

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;

The time complexity is **O(n ^{})**. The execution time took 0 ms on leetcode.

comments powered by Disqus