In this post, we will solve a problem involving dynamic programming without being aware of it.
Problem : Given an array of size N , find the contiguous subarray of size K ( K<=N ) with the largest sum.
What does it mean? 🤔
Contiguous subarray :
Let's assume we have an array A = [ -7 , 4 , -1 , -2 , -5 ] .
What are the possible contiguous subarray we can build from the array A? 🤔
The above diagram shows all possible contiguous sub arrays from the array A. Each array in the above diagram is inside the array A and they are continuous.
What is the total number of contiguous sub arrays we can build from an array A?
Using the diagram given above, we can easily calculate it.
Total number of contiguous sub arrays from an array A of size N ( N = 5 ) :
N + ( N - 1 ) + ( N - 2 ) + . . . . . + 1 = ((N)*(N-1))/2
( We are doing the summation for each row )
If N = 5 , then ( (5)*(5-1) )/2 turns out to be 15 . Therefore, there are 15 possible contiguous sub arrays from an array of size 5.
Now , we will code this up in Python. How to go about it?
Each cell in the above table contains the indices required to build the contiguous subarray from the array A.
Now we will write a program in python to print all possible contiguous sub arrays from the array A.
a = [-7 , 4 , -1 , -2 , -5 ] #creating a list to store the elements
length=len(a) #creating a variable length to store the length of the array a
for i in range( length ): # variable to keep track the row #
for j in range(i,length ): # variable to keep track the column #
for k in range(i,j+1 ): # variable to keep track the particular cell
print(l[k],end=" ") # printing the value at row i,col j,cell k
if j!=length-1:
print(end=" , ") # For formatting
print("\n") # Newline to display like a tableI hope the above code segment is easy to understand. I have given enough details in the comments after each line of code.
Our problem asks us to find a particular subarray from the list of sub-arrays with the maximum sum. A simple solution to the problem is to find the value of sum for each sub arrays and from that, we will return the subarray S with the maximum sum. It is very easy to code in python. We just need to make some simple modifications in the previous code.
Let's do it !!!!
import math # Importing the math library
a = [-7 , 4 , -1 , -2 , -5] # Creating a list to store elements.
length = len(a) # Creating a variable named 'length' to store the length of the list 'a'
max_sum = -math.inf # Before seeing the array , the maximum sum would be -infinity
max_i = -1 # Before seeing the array , the starting index of the subarray would be -1
max_j = -1 # Before seeing the array , the starting index of the subarray would be -1
# -1 doesn't indicate a valid index. It is just to show that we don't know anything before
# actually looking into the array
for i in range(length): # For each row
for j in range(i,length): # For each column
sums = 0 # Initializing the variable 'sum'.
for k in range(i,j+1)
sums+=a[j] # We are calculating the sum of a particular cell.
if sums > max_sum: # We are comparing with the previous maximum.
max_sum = sums # If it is greater than the previou maximum, then we update it.
max_i = i # We are updating the starting index
max_j = j # We are updating the ending index
print("The maximum sum is ",max_sum) # Printing the maximum sum
print("The subarray with maximum sum is ",a[max_i:max_j+1]) # Printing the subarray with maximum sumThe code is well-documented.
The above code segment is very easy to understand. Basically, we are calculating the sum for each possible sub-arrays. We are also keeping track of the maximum sum in a variable. Once we come out of the outermost loop, we print the maximum sum along with the subarray.
What will be the total time taken to execute the above code? Most of the computations we did to solve our problem is in the for loop(s). So , we need to calculate the time taken to run the nested for loop(s) . We are not interested in the exact time taken for executing the code. We can choose an appropriate upper bound to the time it requires to run the code. We will also measure the time taken in terms of number of steps we need to perform in order to solve our problem.
We will include the steps which are dependent on the size of the input and exclude all other steps which are independent of the size of the input. The code snippet sums+=a[k] is fixed and independent of the size of the input. What does it mean? No matter what is the size of the array we are considering , we don't change anything to the code snippet.
The code segment after the innermost loop is also fixed. With all these in mind , we just need to calculate the number of times we visit the for loop(s). Please pause yourselves and digest it .
We can loosely say that ,each for loop runs length times.
Total time taken : length * length * length = ( length ) ^3
We also call it as O( length^3 ) where O denotes Big Oh
The time complexity is little bad!! Why is that?
The time taken to run the code with an array of size length is (length)^3
With (length + 1) , the time taken would be (length+1)^3 which is,
(length)^3 + 1 + 3*(length)^2 + 3*(length) (using the formula : (a+b)^3)
Let us denote T(n) as a function that returns the total time taken to run the code with an input of size 'n'.
Therefore, in our case T(n) = n^3 and T(n+1) = T(n) + 3*n^2 + 3*n
Even if we add a single element to the list, the time taken grows quadratically with the size of the input. It is quite bad. We need to do something. We as a computer programmer always care about the time complexity.
We will tackle this problem step-by-step.
First, we will try to eliminate the innermost loop ( loop with k variable ). If we do so, our T(n) would be T(n) = n^2 . This reduction in time complexity is quite good. First, we need to analyze the steps performed in the innermost loop.
We are basically calculating the sum of the elements in the array from indices i to j in the innermost loop. Then, we are updating the max_sum variable.
Let's assume i = 0 and j = 2 . So , we are calculating the sum of the elements in the array from index 0 to 2 .
sums = a[0] + a[1] + a[2] - > 1
max_sum = max ( max_sum , sums )
For i = 0 and j = 3.
sums = a[0] + a[1] + a[2] + a[3] We are using the result from 1
max_sum = max ( max_sum , sums )
This shows that , we don't need to calculate the sum from scratch. We could use the previously computed sum .
Therefore , we don't need the innermost loop to calculate the sum and update the max_sum variable. We can simultaneously calculate the sum and update the max_sum variable. This eliminates the innermost loop. Pause for a moment and digest it. It is very important to understand this step.
Let's do this in python
import math # Importing the math library
a = [-7 , 4 , -1 , -2 , -5] # Creating a list to store elements.
length = len(a) # Creating a variable named 'length' to store the length of the #list 'a'
max_sum = -math.inf # Before seeing the array , the maximum sum would be #-infinity
max_i = -1 # Before seeing the array , the starting index of the subarray would #be -1
max_j = -1 # Before seeing the array , the starting index of the subarray would #be -1
# -1 doesn't indicate a valid index. It is just to show that we don't know #anything before
# actually looking into the array
for i in range(length): # For each row
sums = 0 # Initializing the variable 'sum'.
for j in range(i,length): # For each column
sums+=a[j] # We are calculating the sum.
if sums>max_sum: # We are comparing with the previous maximum.
max_sum = sums # If it is greater, we update it
max_i = i # We are updating the starting index of the maximum sum subarray
max_j = j # We are updating the ending index of the maximum sum subarray
print("The maximum sum is ",max_sum) # Printing the maximum sum
print("The subarray with maximum sum is ",a[max_i:max_j+1]) # Printing the subarray with maximum sum
The code change is very minimal. Rather than using an another loop to compute the sum, we are simultaneously updating the sum and max_sum variable. To get better understanding, I strongly request the readers to sketch it in the paper or try executing the code in your machine.
We have reduced our time complexity from O ( n^3 ) to O ( n^2 ). It is a great reduction and improvement. Next, we will further reduce it to O ( n )
Here is where, logic and mathematics comes into play. We need to look at the problem in different perspective. Let's get started....
We will first try to visualize what we are doing......
The subarray with maximum sum is present in any of those arrays given in the above diagram. If we remove -7 from the first row , we would get the second row. Similarly it applies for all rows. Therefore if we know the subarray with maximum sum for the second row, then we can find the subarray with maximum sum for the first row. Let's describe it mathematically.
Let M ( i ) be a function which returns the maximum sum for the ith row.
If we know the answer for M ( 2 ), can we find the answer for M ( 1 )?
M ( 1 ) = max ( A[1] + M ( 2 ) , A[1] )
More generally ,
M ( i ) = max ( A[i] + M[i+1] , A[i] )
Can you give some explanation ?
We can easily observe that [ 4 ] is the subarray in the second row which has maximum sum. To compute the subarray with maximum sum for the first row, we need to apply the formula we derived earlier.
M ( 1 ) = max ( -7 + 4 , -7 ) = -3. We can easily verify the solution. If we look at the first row , the subarray with maximum sum is [ -7 , 4 ] and it's maximum sum is -3.
There is a beautiful mathematical proof for the previous claim. The details of it is beyond the scope of this post. I will try to discuss it in the future posts. Everything starts with an intuition
Now we will implement the final solution in python.
import math # Importing the math library
a = [-7 , 4 , -1 , -2 , -5] # Creating a list to store elements.
length = len(a) # Creating a variable named 'length' to store the length of the list 'a'
max_sum = -math.inf # Before seeing the array , the maximum sum would be -infinity
max_overall = -math.inf # Before seeing the array , the maximum sum would be -infinity
max_i = -1 # Before seeing the array , the starting index of the subarray would be -1
max_j = -1 # Before seeing the array , the starting index of the subarray would be -1
# -1 doesn't indicate a valid index. It is just to show that we don't know anything before
# actually looking into the array
for i in range(length-1,-1,-1): # For each row
max_sum = max(a[i],a[i]+max_sum) #Computing the maximum sum starting from i
if max_sum>max_overall:
max_overall=max_sum #Updating the maximum sum
max_i=i
#Small exercise
sums=0
for i in range(max_i,length):
sums+=a[i]
if sums==max_overall:
max_j = i
break
print("The maximum sum is ",max_overall) # Printing the maximum sum
print("The subarray with maximum sum is ",a[max_i:max_j+1]) # Printing the subarray with maximum sum
I kindly suggest the readers to figure out the explanation for the above code segment.
So what is the role of dynamic programming here? In a nutshell, a problem involving dynamic programming has optimal substructure and overlapping sub problems.
Overlapping sub problems: In the starting of the post, we removed the innermost loop (k) due to repeated computations for the variable sum. This repeated computations is loosely called overlapping sub problems
Optimal substructure: Our problem involves finding M ( i ) for all 0<i<length and finding the max ( M( i ) ) . So each problem involves the solution of another problem and combining all of these we get the global solution.
In the future posts, I will try to add some mathematical flavor to it.
I hope it helps !!!