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.

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

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