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! 😀

Why should I learn C++?

Hello folks, this is Punit Sharma from theoryofprogramming.com. Good morning, afternoon or evening accordingly, at whatever time you visit this article. So in this article, I will be providing you an essence of the C++ programming language and why you should use it or rather learn it.
First off, the name. You might be wondering what that “++” is doing there in the name. In many programming languages, ++ is an increment operator. So, C++ is meant to be the next version of C. Well, C++ language is always something that has been viewed as a cryptic programming language. It might sound as a huge understatement but many people are afraid to use or learn C++ just because of the fact that it is vast, and the concepts are too tough to cooperate with. So writing this article serves to be a clear intention to remove this rumor and helping you to use this language because it is beautiful, and will become more beautiful as soon as you get used to it. So let us define C++ in the words stated by its inventor –

“A light-weight abstraction programming language designed for building and using efficient and elegant abstractions and offering both hardware access and abstraction. Doing it efficiently is what distinguishes it from other languages…”       – Sir Bjarne Stroustrup

So Stroustup’s intentions were pretty clear in the above statement. So how many of you agree to what was stated above?
The novice programmers or the ones who are acquainted with Java or C# as the only language in their life might find this statement least interesting. But trust me as well as Bjarne Stroustrup, this programming language brings to you object oriented programming in a taste which you never had with Java or C# when you learnt it for the first time.

How C++ is better?

Getting into insights of the language, the inbuilt sorting function of C++ uses Introsort which is a type of hybrid sorting algorithm (Hybrid of Quicksort and Heapsort) followed by an Insertion Sort on the result. In practical scenarios, in a coding competition, this sort function always serves as a better one than the sorting functions of other object-oriented languages. Let me show an illustration of this. Consider the problem given in the following CodeChef link – https://www.codechef.com/problems/DONUTS.

You can see the rankings with the image below –

C++ in Competitive Programmingcodechef_rank2
 

This problem requires sorting of data at a certain point of the algorithm. And the top 15 submissions are either in C (26.77%) or C++ (73.33%). Moreover, the ones which are submitted in Java or any other language have a worse time and space factor. So C++ provides an extra edge from a competitive programming point of view as well.

Another performance factor where C++ serves as a better option than other OOP languages is in a scenario where objects are being created and destroyed in a loop running in order of 106 or greater than that. Although C++ needs manual allocation and deallocation of memory, it properly deallocates the memory at a good rate in the above situation whereas OOP languages like Java which boasts regarding automatic garbage collection have a garbage collector thread which performs very slowly.
Thus, memory allocations are being done at a faster rate and the rate of destruction being slower. Thus, any scenario like this will result in what we know as “Memory Limit Exceeded”….

Believe it or not, the giants in the gaming industry rely heavily upon C++. Video games still use C++. One example is the Torque engine which can be used for iPhone and Xbox game development. Another reason why this language is great – it is really cross-platform. It is used almost everywhere – PC, Mac, Xbox 360, PS3, cell phones, embedded… you name it. So you can use your skills on almost any platform you feel like. As opposed to many other languages, which are often only useful for one platform. So any aspirant of EA Sports, Nintendo, Sega, Ubisoft etc. should possess proficient skills in language and is a necessity while you submit a resume at this companies.

Not only that, advanced audio and image processing engines use C++. C++ is still used extensively for performance-intensive tasks. For example, a lot of work with video compression and decompression – it’s all C++. Partly because we need the performance, and partly because all the 3rd party libraries which need to use are C++. So it’s easier to integrate with them if we’re using the same language. C++ also leads to a good heat in your pocket or salary++ (the experts say) even if you work with a corporate powerhouse that does not work with the language. Bloomberg, Reuters, and all their bank/trading clients who want low latency market data feeds use C++.
Huff!!!!!! So enough of bragging done….! Hopefully, I was able to justify using the above facts that why C++ should exist and should be learnt and appreciated. There are other facts and features which you will definitely learn and understand in the upcoming articles and get lost in the beauty of C++. Some favourite quotes of mine by Sir Bjarne:-

  • C++ is my favourite garbage collected language because it generates so little garbage.
  • C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off.

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…! 🙂