First Post by StackEdit

This is a test post to check if I can work on stackedit and
them just export the article to WordPress,
hmmm…
let me try

Written with StackEdit.

Maximum Subarray

I am going to write here my explanation for the the maximum subarray problem which is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum.

Here we can find this subarray using different algorithms, Here I shall talk about two of them,

1)  Divide and Conquer :

Time Complexity: O(n log n)
Algorithmic Paradigm: Divide and Conquer

2)  Kadane’s Algorithm : 

Time Complexity: O(n)
Algorithmic Paradigm: Dynamic Programming

1)  Divide and Conquer :

This is a method of designing algorithms where we divide the problem into a number of

sub-problems of smaller size, and we conquer these sub-problems by solving them recursively, ( we keep sending it back for further division until they are a base case of the recursion )

Finally we combine the solutions of these sub-problems to get the required solution of the 

actual problem.

Now we have an array ( lets call it A ) in which there exists a sub-array ( lets call it S )

whose sum is the maximum when compared to other sub-array's,

our objective is to find S's sum.

This subarray could either have the middle element of A ( lets call it mid ) in it or not.

thus we have two cases 

1)  when mid exists inside S :

if this is the case then we take the array and look at the rest of the array from mid's 

point of view. 

here we have chosen A[3] to be the mid ( (7+0)/2 = 3.5 ) 
now to find S, we can break the problem further into 2 parts( the left half and the right half ), S will consist of 2 
sub-arrays S1 and S2 where,
S1 is the maximum subarray in the left half from A[3] to A[0] and 
S2 is the maximum subarray in the right half A[4] to A[7].
these two can be found by iteration, for S1 take A[3] alone then 3,2 then 3,2,1 keep doing this until we find the sum of all elements from mid till the first element (A[0]), all the while keeping track of the maximum sum so gained. so we will have the value of the max subarray in the left of mid ( including mid ) and we can repeat this with the remaining half of the array to find S2's sum.
In the following code I have implemented this leftsum is the S1's sum and rightsum is 
S2's sum. we can thus return (leftsum+rightsum) as S's sum.
In the following code I have implemented this leftsum is the S1's sum and rightsum is 
S2's sum. we can thus return (leftsum+rightsum) as S's sum.

# a is the array, start, mid and end are the respective array indices
def maxsubarray3(a,start,mid,end):
    # if want to find the actual subarray which gives us this maximum value for its sum
    ansstart=mid
    ansend=mid+1

    # we need to find both sums of the left maxsubarray and the right maxsubarray.
    # the sum of which will be the sum of the joint subarray (from i to j) the actual max subarray of a
    # where i and j are such that,
    
    # The subarray from i to mid_index is the maximum you can get
    # from all subarrays where i which is before mid_index

    # keeps track of all the the possible subarray sums
    tempsum=0
    # keeps track of the current top sum (for the left half)
    # initially keep it as a very negative number 
    leftsum=-1
    
    # lets take first half and find the maximum subarray,
    # start from mid and by decrementing ( therefore the -1 )
    # and go till the 1st element ( therefore till array indice start )
    # ( Note that the range(a,b,c) function  produces a list of a,a+c,a+2c,.. so on till b-1 )
    # ( we need to write start-1 to get till start )
    for i in range(mid,start-1,-1):
        tempsum=tempsum+a[i]
        if(tempsum>leftsum):
            # the new top sum
            leftsum=tempsum
            ansstart=i
            
    # just like how we got the leftsum, repeat for right sum.
    tempsum=0 
    rightsum=-1

    # we now check for all possible subarrays in the right half, ie
    # mid+1 till end ( Note that the range(a,b,c) function
    # produces a list of a,a+c,a+2c,.. so on till b-1 )
    for j in range(mid+1,end+1):
        tempsum=tempsum+a[j]
        if(tempsum>rightsum):
            # the new top sum
            rightsum=tempsum
            ansend=j

    return (rightsum+leftsum)

But we should keep in mind we have only covered the case when the max subarray we wish to find has the mid element in it, but then comes the other case.

2)  when mid is not inside S :

In this case we can further divide this case by calling the same function recursively.

until it ends up as the case discussed above or
a trivial case when the array becomes a single element.
I have implemented this with the following code.

# Actual function to solve the max subarray problem
def maxsubarray(a,start,end):
    # Base case when recursion caused the array to finally become a single element
    # the element itself is the only sum, therefore the maximum
    if(start==end):
        return a[start]

    # find mid - an integer as its going to be used as a index
    mid=int((start+end)/2)

    # now we can find the maximum of the 3 cases
    # we divide the array a into 2 parts (0 to mid) and (mid+1 to end), if the "maxsubarray" is a subarray of these 2 halfs we can find so by calling recursively
    # else if the subarray we seek is that which crosses the middle element, then we call the maxsubarray3 function
    return max(maxsubarray(a,start,mid),maxsubarray(a,mid+1,end),maxsubarray3(a,start,mid,end))

So we can see how this algorithm works. I hope. :p

Anime Reviews

One Piece

This was the anime which could be said to have started my addiction! I enjoyed this anime so much that I started downloading it! Its mainly a fun anime with a very thrilling storyline, with plenty of comic scenes and epic battles between people with really crazy powers.But to me its strongest point is the amount of suspense, because of its fast paced storyline you will want to see the next episode.Belive me unlike naruto the story never lags, and oda always manages to both surprise and amuse us.

but you may feel the initial episodes kinda, hmm... slow? anyway.. push through! and you will be rewarded!

A battle to remember!

 

Death Note

This is the anime which is the one I would recommend to anyone who is yet to start watching anime as it is a prime example that lets you see the potential of anime as an art, a method of storytelling. This anime's main attraction is also its gripping story, with no loopholes.We have a protagonist who is too clever for his own good! we see the levels to which a cat and mouse game can reach.

The whole cast :p

 

Naruto

This was one the first anime I had watched, I had really liked it then and got the time to finish it only after I got into a college, This anime is one of the most popular shonen anime of all time, it features a very intricate storyline with a lot of twists and exciting fights, there is a very solid structure in which various powers are held by the characters and most characters are relatable in terms of motive. They explore concepts like friendship, loss of loved ones, being isolated from society, revenge etc in a not so obvious way. The anime has a fatal flaw of trying to fatten the storyline with "fillers" ie episodes not relevant to the main storyline, some of these can be said to serve the purpose of fleshing out the characters. Most of these episodes were in my (and a lot of others opinion) a total drag. Still as of the last episode I watched (371 - shippuden) The wait was really worth it, things are heating up! On the whole naruto was actually totally Awesome!!

The first arc

 

Code Geass

This anime is as I have seen the only anime that comes close to , nah totally beats death note in its particular genre of ultra intelligent protagonists who use complicated strategies, it beats death note (in my opinion) only because of its Kick-ass ending. (Yes its Awesome!) So code geass there is both R1 and R2 (2 seasons), it also (like most anime's which makes you think) has a clean set of rules under which the particular "power" can be used, this ensures that we can get absorbed into the storyline as we can follow all the decisions the protagonist makes as he has to play by the rules. Here the main topic being explored would have to be how all humans are different and if the strongest will survive rule is "right" as are societies meant to help the weak? they ask you to think about the various facets of involving Social Darwinism.

A gem of an anime!

 

Full Metal Alchemist

Well this is among all the top anime lists across the internet, and rightly so! This series is (as far as I know & and have seen heard ) the ONLY anime that you should watch in english Dub, 
Most english dubs are lame, they fail to convey the emotions of the characters properly, ok even I used to watch anime with english audio! hell i didnt understand japanese one bit, but then as naruto (shippuden - second season) didnt have english dub after a number of episodes I had to watch it in english subtitles. And even thought initially I was uncomfortable i have to say it is way way better! See you also get to learn a new language. Naruto itself has run for 220 episodes and Naruto shippuden is at 371, One Piece is at 653! :D (all of 25 mins each). this is just 2 series! the more you watch soon you will be able to understand japanese and maybe even speak rudimentary japanese.
Ok anyway these guys did a superb job of english dubbing this series,The series is based on Alchemy, as you hear in the opening song,
"Human kind can not gain anything without first giving something in return. To obtain something of equal value must be lost. That is Alchemy's first law of equivalent exchange. In those days we really believed that to be the world's one and only truth, But the world isn't perfect, and the law is incomplete. Equivalent Exchange does not encompass everything that goes on here, but I still chose to believe in its principle: that all things do come at a price, that there's an end and a way, that the pain we work through did have a reward, and that anyone who's determined and perseveres will get something of value in return, even if it's not what they're expecting. I don't think of Equivalent Exchange as a law of the world any more. I think of it as a promise between my brother and me, a promise that someday we'll see each other again. "
-Alphonse Eric 
It also has my favorite theme song! I totally fell in love with it.

The awesome powers, and he's too cool too!!

This is basically a copy from http://spider.nitt.edu/~adityap/home.html