O(n) Java Maximum Subarray Simplified Into a Story


  • 0
    Y

    I've always had trouble understanding the concerning the O(n) solution of the maximum subarray even when somehow deriving it myself.
    Here is a story I came up with to help myself understand the algorithm.

    ========================Story========================
    Let's look at this example array
    nums[] = [1,3,-5, 7, 4]
    This array is a timeline of major events of a man's life. In each of these event's the man has the choice of leaving all he currently has and devoting himself to the event. We will use the Maximum Subarray O(n) java solution to evaluate when his life was the best.

    There once was a widower who has worked at a small part time job at the local deli for all of his life so far.
    (int currentsituation = nums[0] = 1, int bestsituationsofar = nums[0] =1)

    The next day he spots a boat on the dock that said "Free! First come first serve!"
    (nums[1] = 3).

    Now he has a choice:
    a. He could leave his job and try to start anew with just the boat and cruise the worldnums[1]
    b. Keep his job and the boat and stay putcurrentsituation+nums[1]

    "What a silly idea!" he remarks. The choice is obvious that his current situation would be better with both the job and the boat so he keeps both.
    currentsituation = Math.max(nums[1],currentsituation+nums[1])
    currentsituation = currentsituation+nums[1];

    His life is now at an all time peak, he has a job and he has a boat!
    if(currentsituation>bestsofar) bestsofar= currentsituation;

    Pretty soon however, things take a turn for the worse. His cranky mother in law across the country somehow convinces him that she must live with him because she fell down a flight of stairs and needs someone to support her.
    (nums[2] = -5).

    He once again has a choice:
    a. Leave all he has and move in with his mother in law (nums[2] = -5)
    b. Have his mother in law come where he lives currentsituation+nums[2]

    "I have a boat and a part time job here! Leaving everything would only make things worse!" He exclaims.
    currentsituation = Math.max(nums[2],currentsituation+nums[2])
    currentsituation = currentsituation+nums[2];

    Clearly his life at the time being is not as good as it once was.
    currentsituation<bestsofar

    The next week, he receives a job to work for a really successful tech company with the option to choose between a multitude of cities. nums[3] = 7;

    He once again has a choice:
    a. Leave all he has and has and move to a new city (nums[3] = 7)
    b. Take the job in his present city and keep everything else he has here currentsituation+nums[3] = 6

    Through deep debilitation he decides the it is better to leave everything and start anew.
    currentsituation = Math.max(nums[3],currentsituation+nums[3])
    currentsituation = nums[3];

    Now with his new job and nothing to worry about his life is at an all time high
    if(currentsituation>bestsofar) bestsofar= currentsituation;

    After a few year, He matches with a girl on okcupid.com. Through countless all night conversations he believes that she is the one he wants the be with. But finds out that she lives all the way in europe.
    "Goddamit!" He says.

    He now has has a choice:
    a. Leave all and has and move to a europe to be with the girl (nums[4] = 4)
    b. keep everything and tell her to move herecurrentsituation+nums[4] = 11

    "I have a good job here, you move to the states!" He tells the the girl.
    currentsituation = Math.max(nums[4],currentsituation+nums[4])
    currentsituation = currentsituation+nums[4];

    The girl flies over and now he's living the dream. Great job and great wife, his life has never looked so bright.
    if(currentsituation>bestsofar) bestsofar= currentsituation;

    He dies the day after the girl moves in with him
    END OF INPUT ARRAY

    We see that the best part of his life of his life was when he has both the job at the tech company and the wife so that's the value we return.
    return bestsofar;

    public class Solution {
        public int maxSubArray(int[] nums) {
            int currentsituation = nums[0],bestsofar = nums[0];
            for(int i = 1; i<nums.length; ++i){
                 currentsituation = Math.max(nums[i],currentsituation+nums[i]);
                if(currentsituation>bestsofar)
                bestsofar= currentsituation; 
            }
            return bestsofar; 
        }
    }
    

    FAQ
    Q: Man that story was bad!
    A: That's not a question and you're bad!

    Q: Was the story an autobiography?
    A: Yes


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.