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.^{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.

Time complexity is O(n^{2}) 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;