Hello world

  • HELLO WORLD
  • FIRST BLOG

Sorry, but i have to write hello world

This is my first article on this Portfolio.
A "Hello, World!" program is traditionally used to introduce novice programmers to a programming language.
"Hello, world!" is also traditionally used in a sanity test to make sure that a computer language is correctly installed, and that the operator understands how to use it.


BACK

Kadane's Algorithm

  • KADANE ALGO
  • DP

How can such a Program works ?

Hey, welcome. Let me guess trying to solve the famous "Maximum Subarray Porblem ?" and came to know about Kadane's Algorithm but after trying hard couldn't figure out how something like that is working, don't worry you've come to the right place.

So, before directly jumping in the Kadane's Algo, first, you need to know about Dynamic Programming.

Dynamic Programming

In simple words, Dynamic Programming is just a fancy way to call remember your past.

Those who cannot remember the past are condemned to repeat it. --Dynamic Programming
Over here you can find a very intuitive and detailed explaination about Dynamic Programming on GeeksforGeeks -- Dynamic Programming from GeeksforGeeks.

Maximum Subarray Problem

The task is to find a subarray (contiguous elements) of the given array that has the largest sum. For example,
[-1, -3, 4, -1, -2, 1, 5, -3]
The answer would be 7 (a subarray).
[0, -1, -5, 0, -4]
The answer would be 0 and so on.

Solutions

  • Brute Force Approach
  • Dynamic Programming Approach
Let's look at each one by one.

Brute Force Approach

It's the very obvious but not a very good solution. In this we'll be going to calculate the sum of every possible subarray and the maximum of those would be the solution. Starting from index 0 calculate the sum og every possible subarray starting with A[1], A[2] and to A[n-1], where n is the size of array.
We can make maximum addition of subarray starting with element A[i] the temporary_max at index i. After going through all the indices, we can have temporary_max for all indicies, and the maximum of those will give us the final solution which is original_max.
Having said that, using Brute-force to solve this problem is trivial. But i don't think this is a clever answer having a time complexity of O(n2). Or frankly, brute-force is not a clever answer most of the times.

Dynamic Programming (Kadane's Algorithm)

Dynamic Programming is the key to success in this problem having time complexity of O(n).
Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (temporary_max is used for this). And keep track of maximum sum contiguous segment among all positive segments (original_max is used for this). Each time we get a positive sum compare it with original_max and update original_max if temporary_max is greater than original_max.


Initialize:
	original_max , temporary_max = 0

Loop for each element in array:
	1. temporary_max = temporary_max + A[i]
	2. if (temporary_max < 0):
		temporary_max = 0
	3. if (original_max < temporary_max):
		original_max = temporary_max

return original_max

Now given below is a python implementation of Kadane's Algorithm


def kadane_Algo(A):
	temporary_max = original_max = A[0]
	for x in A[1:]:
		temporary_max = max(x, temporary_max + x)
		original_max = max(original_max, temporary_max)
	return original_max

Basicaly, at each step what we do is:
  • Check max between temporary_max and temporary_max + current element.
  • If yes, update temporary_max, otherwise current element id=s the largest subarray.
  • Then update the original_max if temporary_max > original_max.
    • Whenever the llop will over, return the original_max.

    Conclusion

    Here we are completed with the Kadane's Algorithm which is a Dynamic Programming solution to Maximum Subarray Sum Problem in runtime of O(n).
    And now I insist you to go and solve this 2D Maximum Subarray Sum Problem by yourself.


    BACK

    About

    • GEEK
    • CODER
    • AMBIVERT
    • ENTHUSIAST

    HI,

    Thanks for arriving here, I am Abhishek kumar Singh. And i am a pre-final year Computer Engineering Student, pursuing my degree from UNIVERSITY OF PUNE, INDIA. I should hope my work reflects that.

    So, I think you guys are here because you want to know about me, HUH! Basically, I am from a small town in BIHAR, INDIA, currently living in Pune.
    Franky, I am not good talking about myself but i'll start by telling you my most favourite things to do, which includes but not limited to-

    • Learning new technologies.
    • Reading Novels (THRILLER).
    • Competitive Programming.
    • Cooking and obviously eating alot.
    • Swimming.
    • And sometimes playing PUBG also.
    I am more of a dog loving person than anything else.

    SKILLS

    • DATA STRUCTURES AND ALGORITHMS
    • OBJECT ORIENTED PROGRAMMING
    • DATABASES
    • LINUX
    • WEB-APP DEVELOPMENT

    LOOK UP FOR ME @

    Follow me @Twitter, See all my latest pics @Instagram and also look at my codes @GitHub.

    WEB SCRAPER

    • PYTHON
    • WEB-CRAWLER

    A simple python web scraper / crawler.

    ABOUT

    For the web crawler two standard library are used - requests and BeautfulSoup4. requests provides a easy way to connect to world wide web and BeautifulSoup4 is used for some particular string operations.
    Here this crawler collects all the product headings and respective links of the products pages from a page of amazon.in . User just need to specify what kind of data or links to be crawled.(Intially it's for title and their links)

    HOW TO RUN

    • Install pip3
      sudo apt install python3-pip
    • Install bs4 module
      pip3 install bs4
    • Compile and run
      python3 scraper.py


    Travel Agency

    • C++
    • OOP-CONCEPT

    A simple Travel / Tourism Agency Project.

    ABOUT

    This Tourism Management Software is written in C++ programming language. Database used in this project is Files *not sql*.

    MODULES

    ADMIN END-USER
    Modify Packages Select Packages
    Modify National Destinations Select National Destinations
    Modify International Destinations Select International Destinations
    View Customer Details Pay for Trip

    Pre-requisites

    • Understanding of inheritance, Virtual and friend functions.
    • Understanding of file handling functions.
    • Basic C++ graphics understanding.