THE CODE NOTE

What is 'Maximal Subarray Problem'(MSP)? Given an array having both positive and negative numbers, we need to find a continuous part of the array whose elements when added gives the largest possible sum. Here are few examples to help you understand the MSP better: 1. consider the array [-1, 2, -1, 3]     Now, here is a list of all the possible subarrays along with the sum of their elements: ELEMENTS SUM start index end index -1 -1 0 0 -1, 2 1 0 1 -1, 2,-1 0 0 2 -1, 2,-1, 3 3 0 3 2 2 1 1 2,-1 1 1 2 2,-1, 3 4 1 3 -1 -1 2 2 -1, 3 2 2 3 3 3 3 3     From, the above table, its obvious that the answer is [ 2,-1, 3].     All other subarrays sum up to a value that is less than 4....

This post serves as a good introduction to the backtracking method which is used widely in various types of problems to find a possible solution. Here we'll be seeing how to solve the classical N-Queens problem using backtracking method. Backtracking : The Wikipedia page  for Backtracking defines it as "a general algorithm in which, we try to incrementally build candidates to the solutions, and discard a candidate as soon as we get to know that the candidate cannot possibly be completed to a valid solution".  If that sounds complicated and confusing, don't worry! Let us understand it by running through a small example. Consider you are trapped in a haunted house with five rooms named A, B, C, D and E. Initially, you are in room A and you need to reach room E to exit the house. Below is an image of the rooms in the house. The arrows in the image indicate the directions in which you can move. For example, you can move to rooms B and C from A but, you ...