Maximum value in a Sliding Window

Problem Statement
Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position.

Example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.

Window position                Max 
---------------               ----- 
[1  3  -1] -3  5  3  6  7       3  
1  [3  -1  -3] 5  3  6  7       3  
1  3  [-1  -3  5] 3  6  7       5  
1  3  -1  [-3  5  3] 6  7       5  
1  3  -1  -3  [5  3  6] 7       6  
1  3  -1  -3  5  [3  6  7]      7

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]

Example 2
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
w= 3
Output :
3 3 4 5 5 5 6

Solution

Method 1: Brute force

The obvious solution with run time complexity of O(nw) is definitely not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window.
Code(Java):

void windowMaxBrute(int arr[], int w)
{
    int j, max;
    int n = arr.length;
    int b[] = new int[arr.length];
    int k=0;//tracker for array b
    for (int i = 0; i <= n-w; i++)
    {
        max = arr[i];
    
        for (j = 1; j < w; j++)
        {
            if (arr[i+j] > max)
                max = arr[i+j];
        }
        b[k] = max;
    }
}

Time complexity - O(n)
Can we do better?

Method 2z : Using Heap (will not work)

Of-course we can do better.  The word max value rings the bell in our head - we can use priority queue?

A heap data structure quickly comes to mind. We could boost the run time to approximately O(n lg w) (Note that I said approximately because the size of the heap changes constantly and averages about w). Insert operation takes O(lg w) time, where w is the size of the heap. However, getting the maximum value is cheap, it merely takes constant time as the maximum value is always kept in the root (head) of the heap.

As the window slides to the right, some elements in the heap might not be valid anymore (range is outside of the current window). How should you remove them? You would need to be somewhat careful here. Since you only remove elements that are out of the window’s range, you would need to keep track of the elements’ indices too. Finding the element to delete in the heap, will take O(w) and O(lgW) time for heapify operation. So, time complexity for n elements, will be again O(n*(w+lgw)) = O(nw), which is same as brute force.

But there are couple of solutions. Lets discuss them one by one. Can we use similar structure to heap, like priority queue?

Method 2a - Maximal value in a queue

A window can be viewed as a queue. When it slides, a number is pushed into its back, and its front is popped off. Therefore, the problem is solved if we can get the maximal value of a queue. There are no straightforward approaches to getting the maximal value of a queue. However, there are solutions to get the maximal value of a stack, which is similar to the solution introduced in the blog “Stack with Function min()”. Additionally, a queue can also be implemented with two stacks (details are discussed in another blog “Queue implemented with Two Stacks”).  If a new type of queue is implemented with two stacks, in which a function max() is defined to get the maximal value, the maximal value in a queue is the greater number of the two maximal numbers in two stacks. Lets call this queue QMax.
Here are the steps:

1. Enqueue w elements into the QMax. Time complexity = O(w)
2. Get the max element from the QMax, and print it, which takes constant time. O(1)
3. Dequeue element from QMax. O(1)
4. Enqueue next element in QMax, O(1)
5. Repeat step 2, 3, 4 until we reach end of array.

Time complexity = O(w + n+n+n) = O(n+w) This solution is workable. However, we may not have enough time to write all code to implement our own queue and stack data structures during interviews. Let us continue exploring a more concise solution.

Method 2b - Saving the maximal value into the front of a queue

Instead of pushing every numbers inside a sliding window into a queue, we try to push the candidates of maximum only into a queue.

Let us take the array {2, 3, 4, 2, 6, 2, 5, 1} as an example and window size as 3 to analyze the solution step by step.

• The first number in the array is 2, we push it into a queue. 
• The second number is 3, which is greater than the previous number 2. The number 2 should be popped off, because it is less than 3 and it has no chance to be the maximal value. There is only one number left in the queue when we pop 2 at the back and push 3 at the back. 
• The operations are similar when we push the next number 4. There is only a number 4 remaining in the queue. Now the sliding window already has three elements, we can get the maximum value at the front of the queue.
• We continue to push the fourth number i.e. 2.  It is pushed at the back of queue, because it is less than the previous number 4 and it might be a maximal number in the future when the previous numbers are popped off. There are two numbers, 4 and 2, in the queue, and 4 is the maximum. 
• The next number to be pushed is 6. Since it is greater than the existing numbers, 4 and 2, these two numbers can be popped off because they have no chance to be the maximum. Now there is only one number in the queue, which is 6, after the current number is pushed. Of course, the maximum is 6.  
• The next number is 2, which is pushed into the back of the queue because it is less than the previous number 6. There are two numbers in the queue, 6 and 2, and the number 6 at the front of the queue is the maximal value. 
• It is time to push the number 5. Because it is greater than the number 2 at the back of the queue, 2 is popped off and then 5 is pushed. There are two numbers in the queue, 6 and 5, and the number 6 at the front of the queue is the maximal value. Now let us push the last number 1. It can be pushed into the queue. 

  It is noticeable that the number at the front is beyond the scope the current sliding window, and it should be popped off.  How do we know whether the number at the front of the queue is out of sliding window? Rather than storing numbers in the queue directly, we can store indices instead. If the distance between the index at the front of queue and the index of the current number to be pushed is greater than or equal to the window size, the number corresponding to be the index at the font of queue is out of sliding window.

The analysis process above is summarized in Table 2.

Step	Number to Be Pushed	Numbers in Sliding Window	Indices in queue	Maximum in Window
1	2	2	0(2)
2	3	2, 3	1(3)
3	4	2, 3, 4	2(4)	4
4	2	3, 4, 2	2(4), 3(2)	4
5	6	4, 2, 6	4(6)	6
6	2	2, 6, 2	4(6), 5(2)	6
7	5	6, 2, 5	4(6), 6(5)	6
8	1	2, 5, 1	6(5), 7(1)	5

Table 2: The process to get the maximal number in all sliding windows with window size 3 in the array {2, 3, 4, 2, 6, 2, 5, 1}. In the column “Indices in queue”, the number inside a pair of parentheses is the number indexed by the number before it in the array.

Code (c++)
We can implement a solution based on the analysis above. Some sample code in C++ is shown below, which utilizes the type deque of STL.

 vector<int> maxInWindows(const vector<int>& numbers, int windowSize)
{
    vector<int> maxInSlidingWindows;
    if(numbers.size() >= windowSize && windowSize > 1)
    {
        deque<int> indices;

        for(int i = 0; i < windowSize; ++i)
        {
            while(!indices.empty() && numbers[i] >= numbers[indices.back()])
                indices.pop_back();

            indices.push_back(i);
        }

        for(int i = windowSize; i < numbers.size(); ++i)
        {
            maxInSlidingWindows.push_back(numbers[indices.front()]);

            while(!indices.empty() && numbers[i] >= numbers[indices.back()])
                indices.pop_back();
            if(!indices.empty() && indices.front() <= i - windowSize)
                indices.pop_front();

            indices.push_back(i);
        }
        maxInSlidingWindows.push_back(numbers[indices.front()]);
    }

    return maxInSlidingWindows;
}

Method 2c - Another solution to get the maximum of a queue

As we mentioned before, a sliding window can be viewed as a queue. Therefore, we can implement a new solution to get the maximal value of a queue based on the second solution to get the maximums of sliding windows.

The following is the sample code:

 template<typename T> class QueueWithMax
{
public:
    QueueWithMax(): currentIndex(0)
    {
    }

    void push_back(T number)
    {
        while(!maximums.empty() && number >= maximums.back().number)
            maximums.pop_back();

        InternalData internalData = {number, currentIndex};
        data.push_back(internalData);
        maximums.push_back(internalData);

        ++currentIndex;
    }

    void pop_front()
    {
        if(maximums.empty())
            throw new exception("queue is empty");

        if(maximums.front().index == data.front().index)
            maximums.pop_front();

        data.pop_front();
    }

    T max() const
    {
        if(maximums.empty())
            throw new exception("queue is empty");

        return maximums.front().number;
    }

private:
    struct InternalData
    {
        T number;
        int index;
    };

    deque<InternalData> data;
    deque<InternalData> maximums;
    int currentIndex;
};

Since this solution is similar to the second solution to get maximums of sliding windows, we won’t analyze the process step by step, and leave it as an exercise if you are interested.

Method 3 - Use Self-Balancing BST

This is similar to 2z.

1. Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size w.
2. Run a loop for i = 0 to n – w
   
   1. Get the maximum element from the BST, and print it.
   2. Search for arr[i] in the BST and delete it from the BST.
   3. Insert arr[i+w] into the BST.

This solution is similar to 2z(using heap), but note that delete is less costly operation, as instead of O(w), we will be taking O(lg w).

Time Complexity:
Time Complexity of step 1 is O(w lg(w)).
Time Complexity of steps 2(a), 2(b) and 2(c) is O(Logk). Since steps 2(a), 2(b) and 2(c) are in a loop that runs n-k+1 times, time complexity of the complete algorithm is O(wLogw + (n-k+1)*Logw) which can also be written as O(nLogw).

Method 4 - Usint Dequeue

This method is similar to method 2b.
We create a Dequeue, Qi of capacity w, that stores only useful elements of current window of w elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.
Code(java)

void windowMaxDeque(int arr[],  int w)
{
    // Create a Double Ended Queue, Qi that will store indexes of array elements
    // The queue will store indexes of useful elements in every window and it will
    // maintain decreasing order of values from front to rear in Qi, i.e., 
    // arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
    Deque <Integer > Qi = new Deque < >(w);
    
    int n = arr.length;
    // Process first w (or first window) elements of array 
    int i;
    for (i = 0; i  < w; ++i)
    {
        // For very element, the previous smaller elements are useless so
        // remove them from Qi
        while ( (!Qi.empty()) && arr[i]  >= arr[Qi.back()])
            Qi.pop_back();  // Remove from rear
 
        // Add new element at rear of queue
        Qi.push_back(i);
    }
 
    // Process rest of the elements, i.e., from arr[w] to arr[n-1]
    for ( ; i  < n; ++i)
    {
        // The element at the front of the queue is the largest element of
        // previous window, so print it
        cout  < < arr[Qi.front()]  < < " ";
 
        // Remove the elements which are out of this window
        while ( (!Qi.empty()) && Qi.front()  <= i - w)
            Qi.pop_front();  // Remove from front of queue
 
        // Remove all elements smaller than the currently
        // being added element (remove useless elements)
        while ( (!Qi.empty()) && arr[i]  >= arr[Qi.back()])
            Qi.pop_back();
 
         // Add current element at the rear of Qi
        Qi.push_back(i);
    }
 
    // Print the maximum element of last window
    System.out.println(arr[Qi.front()]);
}
 
// Driver program to test above functions
public static void main(String[] args)
{
    int arr[] = {12, 1, 78, 90, 57, 89, 56};
    int w = 3;
    windowMaxDeque(arr, w);
}

Please suggest, if you have some other methods.
Source

• http://myqc.wordpress.com/2012/08/13/amazon-interview-questions-cheatsheet/
• http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/ 
• http://articles.leetcode.com/sliding-window-maximum/ 

Read More

Container With Most Water

http://n00tc0d3r.blogspot.in/2013/02/container-with-most-water.html

Read More

Maximum Area Rectangle in Histogram using linear search via stack of incomplete sub problems

We have already discussed lots of solution to solve this here, and using the stack to achieve is one of them.

Problem

Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram.

(Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.)

Consider the histogram below:

Hieghts = { 6,2,5,4,5,1,6}

Max area of the rectangle:

Max area = 4 * 3 = 12



This problem seems like container-with-most-water problem discussed here. But the difference is that we are not using two "wood boards" to make a bucket, but using several boards with different heights.

Brute force solution

A straightforward answer is to go for each bar in the histogram and find the maximum possible area in histogram for it. Finally find the maximum of these values. This will require O(n^2) time but this will be huge if we have a big histogram with thousands of bars. 




Solution with Stack

Here we will use stack (of-course it rings the bell that recursive solution is also possible).

 Time complexity here will be O(n) as we will see. Though as discussed here, there are many better solutions available.

Here we process the elements from left to right order, and maintain a stack of information about started but yet unfinished histograms.The point of this algorithm is to maintain a stack where higher element is always greater or equal to the lower element. Why do we need to maintain that kind of stack? Because if we have a non-decreasing list, we can easily calculate the maximum area in one scan.

We just need to compare: height[i] * (n – i) for every i. (It will be clear in sometime).
So how do we maintain this stack? If we keep seeing larger element, we just need to push them onto the stack. If we see a smaller (compared to the top element on the stack) element, we need to do two things:

1. Pop the stack until we can maintain the non-decreasing order. Pushing the smaller element for m times, where m = number of popped elements.
2. Keep track of the maximum area that cause by those pop.

For example, we have height = {1,3,5,7,4}.
We push onto the stack for {1,3,5,7} then we see 4. 4 is less than 7, so we need to pop. We stop popping until we see 3. However many times we pop, we push 4 onto the stack. Therefore the resulted stack would be {1,3,4,4,4}. Because of popping 7, we need to remember that the maximum area that contains 7 is 7. The largest area that contains 5, the other element which get popped, is 10. So we take that down. We then finish processing all the elements in the original array and end up with a non-decreasing stack {1,3,4,4,4}. We can compute the largest area of this stack, which is 4*3 = 12. Since 12 is larger than the previous largest, 10, we output 12.

Code in java

public int largestRectangleArea(int[] height) {
    Stack<Integer> stack =
        new Stack<Integer>();
    int max = 0;
    int i = 0;
    while(i < height.length) {
        if(stack.isEmpty() ||
            height[i] >= stack.peek()) {
            stack.push(height[i]);
            i++;
        }
        else {
            int count = 0;
            while(!stack.isEmpty() &&
                stack.peek() > height[i]) {
                count++;
                int top = stack.pop();
                max = Math.max(max, top * count);
            }
            for(int j = 0; j < count + 1; ++j) {
                stack.push(height[i]);
            }
            i++;
        }
    }
     
    int count = 0;
    while(!stack.isEmpty()) {
        count++;
        max = Math.max(max, stack.pop() * count);
    }
    return max;
}

Dry running the code



Sources
http://tech-queries.blogspot.in/2011/03/maximum-area-rectangle-in-histogram.html
http://blog.theliuy.com/largest-rectangle-in-histogram/
http://tianrunhe.wordpress.com/2012/07/26/largest-rectangle-in-histogram/

Read More

Arrays Index

Rotated array

• How to rotate an array?

Rotated sorted array

• Find the minimum element in the rotated sorted array.
• Find the rotation count in rotated sorted array
• Find Nth largest element in the rotated sorted array
• Search an element in the sorted rotated array 

Sorted Infinite Arrays

• Searching the element in sorted infinite array of integers
• Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 . 

Binary or only few integer arrays

• Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .
• Sorting binary array - Array containing only 0 and 1 OR two color sort
• Sorting Array of Three Kinds or The Dutch National Flag Problem OR three color sort 

Two sorted arrays

• Median of 2 sorted arrays of equal size n
• Intersection of two sorted lists or 2 sorted arrays
• Given two sorted arrays of size m and n respectively (m >> n), how to merge them together?
• Merge 2 sorted arrays of size n and 2n, but having only n elements each

2D arrays

• Maximum size square sub-matrix with all 1s
• spiral printing of a two dimensional array
• Row consisting max continuous chain of 1’s in an n * n grid

2D sorted arrays

• Searching in 2D array : Elements being sorted horizontally and vertically
• Find row with maximum number of 1s in sorted matrix

Read More

Maximum weight independent set (WIS) graph problem using DP

Input - A path graph G = (V,E)
with non - negative weights on vertices

eg.Consider the graph with vertex weights - 1,4,5,4

Desired output - subset of non-adjacent vertices - an independent set of maximum total weights.

Solutions
Brute force
polynomial time, so lets do better.

greedy approach
Greedy algos are easy to implement but are sometimes not correct. To apply greedy approach here we have to iteratively choose the max-weight vertex not adjacent to any previously chosen vertex.

So, in the graph above, greedy will fail. Why?
To begin with greedy algo will pick the most weighted vertex, with weight 5, and as it picks 5 it is blocked on both side to pick any other vertex i.e vertices with weight 4 and 4, but it picks 1, which leads to total cost of 6, which is incorrect.

 A divide and conquer approach

We divide the path graph in 2 , so max in 1st part is 4 and max in 2nd part is 5, and now as the recursion is complete, we merge back the solution, but OOPS, the nodes are adjacent, which is again incorrect. As the graph is small, we can think of some way of avoiding this, but in very very big graphs, it will make it very complicated. So, greedy is myopic in this sense.

So, all the paradigms have failed till now, but lets see if Dynamic programming can be of any help.

Dynamic programming
Lets now work on dynamic programming.

Dynamic Programming
Critical step - Reason about structure of an optimal solution.

Motivation - This thought experiment narrows down the set of candidates for the optimal solution, can search through small set using brute force search.So, we have to think that we do have optimal solution, i.e. guessing and finally get that solution.


Notation - Let S ⊆ V be a max-weight independent set (WIS)
Let v_n = last vertex of path (i.e. the rightmost vertex).

Case1 - v_n  is excluded from optimal solution S
Suppose v_n  is excluded from optimal solution S.  ie. v_n ∉ S.
Let G' = G with vn deleted.

Note : S also an IS of G'.
Note : S must be a max weight IS of G' - if S* was better it would also be better than S in G [contradiction]

Case 2 - Suppose v_n ∈ S ..i.e. S does include vn
Note - previous vertex v_n-1 ∉ S due to adjacency rule.

Let G'' = G with v_n-1 , v_n deleted

Note : S - {v_n} is an IS of G''.
Must in fact be a max weight IS of G'' - if S* is better than S, in G'' , then S* U {v_n} is better than S in G [contradiction]

We did all this because - the optimal solution is to select the case where either v_n is there or its not there. So, lets take either case, and see whichever is better. So, if vn is not included, than we have to search for WIS in G' and if it is included we have to search for WIS in G''. This is kind of brute force, but it is far better.

So, now we have a thought process, we have to come up with algorithm.
If we knew whether or not we exclude the last vertex v_n from the optimal solution, because optimal soluton depends on it. So, the optimal solution can have 2 possibilities - either it excludes the final vertex or the last vertex and get max WIS from G' or it includes the last vertex then it gets WIS from G''.

So, if we somehow knew which case we are in,we can just solve this by recursing on rest of the graph based on the case.But there is no way to find this way, so lets resort to brute force. We apply crazy solution that we can compute the solution recursively going into both cases and choosing the path which gives the better result.

Proposed algorithm
Now suppose we apply crazy solution that we can compute the solution recursively going into both cases and choosing the path which gives the better result.

  Recursively compute S1 = max-wt IS of G'
  Recursively compute S2 = max-wt IS of G''
  return S1 or S2 U {vn} - whichever is better

Good news - It will work.
Bad news    - So, this looks like a brute force, as we are going through almost all vertices, hence takes exponential time.

The $64000 Question(Moving towards memoization)
So, this brings us to important question - Over these exponentially many recursive calls, how many distinct sub-problems are ever get solved by this algorithm? Answer is θ (n).

So, even if there are exponential calls, we have to solve only distinct  θ (n) sub problems.

This is because when we start from right vertex, we will be taking it or leaving it, then we will skip 1 vertex and like wise go through till we pluck all the vertices. So, in first recursive call you may pluck out one vertex from the right, and 2nd recursive call you may pluck out 2, but both from the right. So, we always pluck the vertex from the right.

So, we have to remove the redundancy, as we dont have to solve the same problem more than once. So, we will be using a technique called - memoization, where we will cache the sub problem as soon as we see it.

So, we have to see if we have seen that problem earlier, just skip but if we not then just go recursively and solve it.

But more better way is to shun this top down recursion, and accept bottom up iterative algorithm.

Let Gi is the subset of G, containing 1st i vertices of G

Plan - Populate array A bottom up, i.e. left to right with A[i] = IS of Gi

Initialization : A[0] = 0 and A[1] = w1

Main loop : For i = 1, 2, ...,n   {

                      A[i] = max (A[i-1] , A[i-2]+wi)

(max of case 1 or case 2)

This is same as recursive , only thing is it skips the redundant cases. Also, note that this algorithm gives us the max weight in the array element A[n] and not the solution containing the vertex path.

Time complexity: O(n)

Applying this algorithm on above problem
So, our path graph is 1,4,5,4 :

 So, as initialization we will have A[0] = 0 and A[1] = w1 = 1. Our array looks like:

Now,A[2] = max ( A[i-1], A[i-2]+w2) , where i = 2
A[2] = max( 1, 0 + 4) = 5.

Similarly we go on and array becomes:

So, here we have got 8 as the maximum value, as it is the max value(if we take vertices b and d, with weights 4 and 4). So, we notice here that the algorithm gives us optimal value and  not the optimal solution.

Getting the Optimal solution from the Optimal value
 We can do 2 things to get optimal solution:

1. Put in the optimal solution value at the time of construction [Not recommended, hence we didnt do the same in algorithm above]
2. Reconstruct the path as and when required using array A which we created in algorithm above.

 So, lets follow point 2. How to trace back? Key point - We know that vertex vi belongs to max weight IS of Gi. So, our last element in the array is either included in optimal solution or not. So, if last element is higher than element just before it, then it is included and similarly for other elements.

Let A = filled in array A
i = n
Let S = {}

while i>=1{
   if(A[i-1]>=A[i-2])
      decrease i by 1
   else
      add vi to S, 
      decrease i by 2

return S

Running time : O(n)

Now we can define dynamic programming.Key ingredients of dynamic programming:

1. Identify a small number of sub problems
   eg. compute the max-weights IS of Gi, for i=0,1,2,...n
2. Quickly and correctly solve "larger" sub problems given solutions to "smaller sub problems"
   usually via recurrence such as A[i] = max(A[i-1],A[i-2]+wi)

Read More

Sequence Alignment using Dynamic Programming

Problem :
Input :
2 strings or sequence of characters i.e. X = x1x2...xm, Y = y1y2...yn

Goal - To define the similarity matrix between the 2 sequences with best alignment. This is based on penalty score, called Needleman/Wunsch score.

Eg. consider the sequence - AGGGCT and AGGCA , best alignment here is:
AGGGCT
 |  |  |      |
AGG - CA

Penalty
Penalty = penalty of match+penalty of difference + penalty of space

In the problem all the penalties are given.


For this example, the two sequences to be globally aligned are G A A T T C A G T T A (sequence #1)
G G A T C G A (sequence #2)
So M = 11 and N = 7 (the length of sequence #1 and sequence #2, respectively)
A simple scoring scheme is assumed where

• S_i,j = 1 if the residue at position i of sequence #1 is the same as the residue at position j of sequence #2 (match score); otherwise
• S_i,j = 0 (mismatch score)
• w = 0 (gap penalty) 

Applying the DP
 Now lets apply the DP here. Suppose X is x1x2...xm, and Y=y1y2...yn. In this case, the last array position can have 3 possibilities (in top and bottom sequence respectively):

1. xm and yn are aligned
2. xm is aligned with space / gap
3. space / gap  is aligned with yn

(Note that space cannot align with space, as it will be useless)

Optimal substructure
Let X' = X- {xm} , Y' = Y - {yn}
If case 1  holds, then induced alignment of X' and Y' as X' and Y' are of same size.
Similarly for case 2 and case 3.

Relevant sub problems 
Here sub problems get smaller, by plucking the characters from either 1st string or 2nd string or both. Hence we need to track how many characters we have plugged, and hence we need 2D array to keep track tof 2 things.


Optimal solution for penalty:
Let P denotes the Penalty here.
Lets consider the case 1 - xm and yn are aligned
Mij = Sij  + M(i-1)(j-1)

Case2 - xm is aligned with space / gap
Mij = w + M(i-1,j)

Case 3 - space / gap  is aligned with yn
Mij = w + M(i,j-1)

Mi,j = MAXIMUM[
     Mi-1, j-1 + Si,j (match/mismatch in the diagonal),
     Mi,j-1 + w (gap in sequence #1),
     Mi-1,j + w (gap in sequence #2)]

In case the penalties are such that we are given penalty Sij of mismatch is higher than penalty of match, then we have to use minimum function.
 
Three steps in dynamic programming

1. Initialization
2. Matrix fill (scoring)
3. Traceback (alignment)

Initialization Step-edge cases
The first step in the global alignment dynamic programming approach is to create a matrix with M + 1 columns and N + 1 rows where M and N correspond to the size of the sequences to be aligned.
Since this example assumes there is no gap opening or gap extension penalty, the first row and first column of the matrix can be initially filled with 0.(Note in normal problem if Sgap is not 0, then use it some as i.gap)

Matrix Fill Step

One possible (inefficient) solution of the matrix fill step finds the maximum global alignment score by starting in the upper left hand corner in the matrix and finding the maximal score M_i,j for each position in the matrix. In order to find M_i,j for any i,j it is minimal to know the score for the matrix positions to the left, above and diagonal to i, j. In terms of matrix positions, it is necessary to know M_i-1,j, M_i,j-1 and M_{i-1, j-1}.
For each position, M_i,j is defined to be the maximum score at position i,j; i.e.

Mi,j = MAXIMUM[
     Mi-1, j-1 + Si,j (match/mismatch in the diagonal),
     Mi,j-1 + w (gap in sequence #1),
     Mi-1,j + w (gap in sequence #2)]

Note that in the example, M_i-1,j-1 will be red, M_i,j-1 will be green and M_i-1,j will be blue.
Using this information, the score at position 1,1 in the matrix can be calculated. Since the first residue in both sequences is a G, S_1,1 = 1, and by the assumptions stated at the beginning, w = 0. Thus, M_1,1 = MAX[M_0,0 + 1, M_{1, 0} + 0, M_0,1 + 0] = MAX [1, 0, 0] = 1.
A value of 1 is then placed in position 1,1 of the scoring matrix.

Since the gap penalty (w) is 0, the rest of row 1 and column 1 can be filled in with the value 1. Take the example of row 1. At column 2, the value is the max of 0 (for a mismatch), 0 (for a vertical gap) or 1 (horizontal gap). The rest of row 1 can be filled out similarly until we get to column 8. At this point, there is a G in both sequences (light blue). Thus, the value for the cell at row 1 column 8 is the maximum of 1 (for a match), 0 (for a vertical gap) or 1 (horizontal gap). The value will again be 1. The rest of row 1 and column 1 can be filled with 1 using the above reasoning.

Now let's look at column 2. The location at row 2 will be assigned the value of the maximum of 1(mismatch), 1(horizontal gap) or 1 (vertical gap). So its value is 1.
At the position column 2 row 3, there is an A in both sequences. Thus, its value will be the maximum of 2(match), 1 (horizontal gap), 1 (vertical gap) so its value is 2.
Moving along to position colum 2 row 4, its value will be the maximum of 1 (mismatch), 1 (horizontal gap), 2 (vertical gap) so its value is 2. Note that for all of the remaining positions except the last one in column 2, the choices for the value will be the exact same as in row 4 since there are no matches. The final row will contain the value 2 since it is the maximum of 2 (match), 1 (horizontal gap) and 2(vertical gap).

Using the same techniques as described for column 2, we can fill in column 3.

After filling in all of the values the score matrix is as follows:

Traceback Step

After the matrix fill step, the maximum alignment score for the two test sequences is 6. The traceback step determines the actual alignment(s) that result in the maximum score. Note that with a simple scoring algorithm such as one that is used here, there are likely to be multiple maximal alignments.
The traceback step begins in the M,J position in the matrix, i.e. the position that leads to the maximal score. In this case, there is a 6 in that location.


Traceback takes the current cell and looks to the neighbor cells that could be direct predacessors. This means it looks to the neighbor to the left (gap in sequence #2), the diagonal neighbor (match/mismatch), and the neighbor above it (gap in sequence #1). The algorithm for traceback chooses as the next cell in the sequence one of the possible predacessors. In this case, the neighbors are marked in red. They are all also equal to 5.

Since the current cell has a value of 6 and the scores are 1 for a match and 0 for anything else, the only possible predacessor is the diagonal match/mismatch neighbor. If more than one possible predacessor exists, any can be chosen. This gives us a current alignment of

    (Seq #1)      A 
                  |
    (Seq #2)      A

So now we look at the current cell and determine which cell is its direct predacessor. In this case, it is the cell with the red 5.

 


The alignment as described in the above step adds a gap to sequence #2, so the current alignment is

    (Seq #1)     T A
                   |
    (Seq #2)     _ A

Once again, the direct predacessor produces a gap in sequence #2.

After this step, the current alignment is

      (Seq #1)     T T A
                       |
                   _ _ A 

Continuing on with the traceback step, we eventually get to a position in column 0 row 0 which tells us that traceback is completed. One possible maximum alignment is :

Giving an alignment of :

          G A A T T C A G T T A
          |   |   | |   |     | 
          G G A _ T C _ G _ _ A 

An alternate solution is:

Giving an alignment of :

          G _ A A T T C A G T T A
          |     |   | |   |     | 
          G G _ A _ T C _ G _ _ A

 
There are more alternative solutions each resulting in a maximal global alignment score of 6. Since this is an exponential problem, most dynamic programming algorithms will only print out a single solution.

Time complexity

O(m n)
m = size of sequence X, and n = size of Y

 

Read More