Dynamic Programming – Kadane’s Algorithm

Hello people..! In this post, we will look at a simple dynamic programming based algorithm which is the optimal solution to the Maximum Sum Subarray Problem. Try to focus on how the approach of dynamic programming is applied rather than just trying to understand the main algorithm. Now, let us define the problem.

Maximum Sum Subarray – Given an array A[1, 2, 3, … n]. We need to find that subarray A'[i, i + 1, i + 2, … j] where 1 ≤ i ≤ j ≤ n, where the sum of all the elements in A’ is maximum.

In simpler terms, we need to find that contiguous portion of an array where the sum is maximum.

Brute force approach

Brute force approach would be to look at all the sub-arrays starting with A[i] –

maxSum ← -∞

for i ← 1 to n
        sum ← 0
        for j ← i to n
                sum += arr[j]

                maxSum ← max(maxSum, sum)

return maxSum

This is algorithm is simple but it takes O(N²) time. The problem with this algorithm is that we are not able to save computation by using the solutions to the problems we already solved.

Let us re-write this algorithm slightly differently! Pay attention! Instead of starting from A[i] and going forward looking for maximum, this time, let us start at A[i] and go backward doing the same thing, finding the maximum. Here is the algorithm –

maxSum ← -∞

for i ← 1 to n
        sum ← 0
        for j ← i to 1   // decrement j
                sum += arr[j]

                maxSum ← max(maxSum, sum)

return maxSum

What we are doing is instead of looking at all the sub-arrays starting with A[i], we will look at all the sub-arrays ending with A[i]. This still runs in O(N²) time. So, what’s so special about this? Let is say we have an array A = {-1, 2, 3, -4}. The above algorithm would work on this algorithm something like this –

  • for i = 1 ⇒ max( sum(-1) )
  • for i = 2 ⇒ max ( sum(2), sum(2, -1) )
  • for i = 3 ⇒ max ( sum(3), sum(3, 2), sum(3, 2, -1) )
  • for i = 4 ⇒ max ( sum(-4), sum(-4, 3), sum(-4, 3, 2), sum(-4, 3, 2, -1) )

The solution would be the maximum of all iterations. If you notice, in each iteration, we are finding the maximum sum of all the sub-arrays ending with A[i]. Let us say we store this result in an array maxSum[i].

Kadane’s Algorithm states that,

kadane-algorithm-equation

In simple terms, it states that, the maximum sum sub-array ending with A[i], is either the element A[i] itself, or A[i] combined with the maximum sum sub-array ending with A[i – 1], whichever is the greater one.

Ponder upon this for a while. Using the above intuition we can re-write the above iterations as –

  • for i = 1 ⇒ max ( -1 ) ⇒ maxSum[1] = -1
  • for i = 2 ⇒ max ( 2, 2 + -1 ) ⇒ maxSum[2] = 2
  • for i = 3 ⇒ max ( 3, 3 + 2 ) ⇒ maxSum[3] = 5
  • for i = 4 ⇒ max ( -4, -4 + 5 ) ⇒ maxSum[4] = 1

And as before, the solution would be the maximum of all the elements in maxSum array. For the sake of simplicity, we used the array maxSum[], but we only need the previous iteration’s result to compute the current iteration result. So, we can make it a variable. So our iterations change into –

  • for i = 1 ⇒ maxSum = -1
  • for i = 2 ⇒ max ( 2, 2 + -1 ) ⇒ maxSum = 2
  • for i = 3 ⇒ max ( 3, 3 + 2 ) ⇒ maxSum = 5
  • for i = 4 ⇒ max ( -4, -4 + 5 ) ⇒ maxSum = 1

Why was the first iteration written like that? It is the trivial case. The maximum sum sub-array ending with the first element is the first element itself. And for each iteration, we could keep a global variable, say maxGlobalSum, which keeps track of maximum of all maxSum values.

If you have understood everything up to now, you should be able to code the algorithm very easily. If you didn’t understand, please give a couple more readings and try to code again. Feel free to ask your doubts in the comments!

If you are stuck with the algorithm, you can use my code as a reference –

CJava
    
    

This algorithm runs in O(N) time and uses O(1) space. I hope you have developed an idea of how to think in the dynamic programming way. To get a dynamic programming algorithm, we just have to analyse if where we are computing things which we have already computed and how can we reuse the existing solutions. Keep practising..! Happy Coding! 😀

Trie Tree Practise – SPOJ – DICT

Hello people..! In this post we will talk about solving another competitive programming question based on trie tree. I will take up the SPOJ problem – DICT. This is a little harder than the previous trie tree practise problem, PHONELST. Now, read the problem statement carefully a couple of times. Just so that you don’t need to open SPOJ in another tab, I have posted the problem statement below –

Problem Statement
Input Specification
Output Specification
Sample Input
Sample Output

Problem in terms of Trie Tree

Firstly, we will insert the N words into a trie tree. Then, for each K prefix words –

  • We will traverse the trie tree for this word.
  • If it exists, we will lexicographically print the trie tree, with that node as the root. And obviously, we add the prefix to whatever we will print.
  • If the word doesn’t exist at all, that is, while traversing, we would reach a dead-end (no children) node before the prefix word is fully processed, we will simply return from our traversal and print “No match.”.

So, what all do you need to solve this?

  • Trie Tree insertion method.
  • Trie Tree inorder traversal method (lexicographical print)

We can discard any other methods such as delete. We will need another method for searching whether a given word is present in the trie tree or not, in O(L) time, where L is the length of the word. So, take your implementation of trie tree and get it ready for solving the question by making these changes.

searchWord() Method

This is a simple trie tree traversal method, where we traverse the trie tree based on a given word. We look at each character of the word and go to the corresponding edge, in the trie tree. If there is no edge, we return null. If we have reached the end successfully, we return the node where the word ends. Try to code this procedure, you can refer to my code if you are stuck.

C++
struct node * searchWord(struct node * TreeNode, char * word)
{
    while (*word != '\0') {		// while there are alphabets to process
        if (TreeNode->children[*word - CASE] != NULL) {
        	// there is an edge corresponding to the alphabet
            TreeNode = TreeNode->children[*word - CASE];
            ++word;
        } else {
        	// there is no edge corresponding to the alphabet
            break;
        }
    }
 
    if (*word == '\0') {
    	// the word was completely processed
        return TreeNode;
    } else {
    	// word is not there in trie tree
        return NULL;
    }
}

lexicographPrint() Method

This method will have very minor changes from your original method. According to our intuition, we will call this method based on the output of the searchWord method. If it is null, then it is “No match.”. If it is not null, then we begin the lexicographPrint from that node.
This method will carry an extra parameter, which will be the prefix word. Everytime we hit a leaf node, we first print the prefix word and then the remaining word traversed in this method.
Example, in the sample test case, the prefix word was “set”, so, the searchWord would return us, the location of the T node in S → E → T traversal. Then, we begin our lexicographPrint, and when we hit the end of “setter” word, we will print the “set” prefix, and the “ter” word which we gained from the lexicographPrint method.
Try to code these modifications in your code, you can refer to my code if you are stuck.

C++
 
void lexicographPrint(struct Node * trieTree, vector<char> word, char * prefix)
{
    int i;
    bool noChild = true;
 
	if (trieTree->wordEnding && word.size() != 0) {
        vector<char>::iterator itr = word.begin();
		
		printf("%s", prefix);	//	print the prefix
        
		while (itr != word.end()) {
			// print the rest of the word
            printf("%c", *itr);
            ++itr;
        }
        
        printf("\n");
    } 
 
    for (i = 0; i < ALPHABETS; ++i) {
        if (trieTree->children[i] != NULL) {
            noChild = false;
            word.push_back(CASE + i);
            lexicographPrint(trieTree->children[i], word, prefix);
            word.pop_back();
        }
    }
 
    word.pop_back();
}

Putting the pieces together

Now combine your modules and prepare your main function as per the problem statement. You can refer to my code if you are stuck.

    

Word of Caution –

  • The output in the case of a mismatch is “No match.”, not “No match”.
  • The time limits are pretty tight, so your methods should be tidy.

I hope that you were able to solve this problem using a trie tree. Feel free to comment if you have any doubts. If you have any bugs in your code, I’d be glad to help, but don’t comment your entire code in the comment, please leave Ideone or PasteBin links, or if you don’t want to show your code publicly, you can fill up the response form below to mail your code to me. I will respond as soon as I can. Keep practising… Happy Coding…! 🙂

Trie Tree Practise – SPOJ – PHONELST

Hello people..! In this post I will show you how to get started with solving Trie Tree based questions in competitive programming. Learning a data structure is different from solving competitive coding questions based on that data structure. In this post, I take up a very simple question so that your confidence is boosted.
We will look at the SPOJ problem – Phone List. It is a very straight forward problem. Just so that you don’t need to go to SPOJ in a new tab, I’m putting the problem statement here.

Problem Statement

Phone List Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

• Emergency 911

• Alice 97 625 999

• Bob 91 12 54 26

In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

The Problem in terms of Trie Tree

We are supposed to check if any word is a prefix of any other or not. Now, there might be a hundred ways to solve this problem, but we will do this using a trie tree so that we can get confident in using the data structure, and so that we can attempt tougher ones based on a trie tree. All throughout my explanation, I will be referring to the implementation in my post on Trie Tree.
What we will do to solve this problem is that, we will insert the words into the trie tree one-by-one, and we will check for the prefix word criteria as we are inserting. Now, there are 2 cases.

Case – 1 – Prefix word is already inserted

This is the sample test case. Consider this test case –

Input
face
facebook

So, what I said we will do is that, we will be inserting the words one-by-one. So, when we insert the word “face”, no problems occur. But while inserting the word “facebook”, we would travel to the nodes F → A → C → E. And at the node E, we would have some indication that this node is a leaf node, that is, some word ends here. In my implementation, this can be indicated by –

if (temp->occurrences.size() == 0) {
	// not a leaf node
} else {
	// a leaf node, thus this is
	// the end of the prefix word
}

If we encounter this situation, we know that the result will be NO.

Case 2 – Prefix word is about to be inserted

This is just the opposite of the previous case, consider the test case –

Input
facebook
face

We won’t have any issues while inserting “facebook”. But when inserting “face”, we traverse F → A → C → E. And in the end of insertion, we see that there is a child node to the node E. Which means that there is a bigger word which ends somewhere deep down the trie tree. Which means that we just inserted the prefix word. We could check this by traversing the children array –

for (i = 0; i < ALPHABETS; ++i) {
	if (temp->children[i] != NULL) {
		// The newly inserted word is
		// prefix to another word
	}
}

In this case too, the answer would be a NO. For every other case, the answer would be a YES.

So, try to code this problem. Take your code of the trie tree, remove the unnecessary things first, like the delete function or print function or any others which we won’t need. As fas as I know, the insert function is all that you will need. And try to make the changes required for the test cases.
Your insert function could return a true or a false, depending on whether the insertion encountered a prefix test case or not. Take time to think about it and try to code it. If you get stuck, you can refer to my code below –

    

A word of caution –

  • Even if you did encounter a prefix word very early, don’t break out of the input, as you will disturb the input for the next test case.

I hope that you were able to solve this problem using a trie tree. It is simple and a prefect problem to start your trie tree streak in competitive coding. Feel free to comment if you have any doubts. If you have any bugs in your code, I’d be glad to help, but don’t comment your entire code in the comment, please leave Ideone or PasteBin links, or if you don’t want to show your code publicly, you can fill up the response form below to mail your code to me. I will respond as soon as I can. Keep practising… Happy Coding…! 😀