Maximum Subarray

Tags: leetcode dp java python

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. I often start with a brute force approach without fretting about time complexity. Later I try to improve my algorithm for a better efficient 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.¹

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.

• Java
• Python

Time complexity is O(n²) and has Time Limit Exceeded on leetcode.

More efficient solution

We can use Kadane algorithm to solve. It scans 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;

• Java
• Python

The time complexity is O(n).

Footnotes

---

1. Leetcode

   ↩

2. Github Repository

   ↩

---

comments powered by Disqus