Largest sum contiguous subarray

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

Problem:

From Wikipedia :
In computer science, the Largest sum contiguous subarray is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Solution :

There are multiple solution to solve this problem:

Solution 1:

Use two loops and try each combination of array elements to find maximum sum.
Time complexity : O(N^2)

Solution 2:

Kadane ‘s algoritm
I have discussed Kadane ‘s algorithm in previous post. You can refer it.
Time complexity : O(N)

Solution 3:

Dynamic Programming:
You can use dynamic programming to solve this problem.
Lets say array be arr[] and maximum sum upto index i is maxSum(i)
Logic which can be used for dynamic programming:

So it can be define as
Max sum at index i is maximum of (max sum upto i-1 + current element , current element)
Java code  :

Time complexity : O(N)

Java Program to find largest sum contiguous subarray:

When you run above program, you will get below output:


import_contacts

You may also like:

Related Posts

  • Get current year in java
    13 July

    Get current year in Java

    Table of ContentsUsing Date and SimpleDateFormatUsing CalendarUsing LocalDateUsing LocalDateTimeusing ZonedDateTimeUsing OffsetDateTimeUsing Instant and ZoneIdUsing Instant and ZoneOffsetConclusion In this post, we will see how to get current year in Java. Using Date and SimpleDateFormat The Date class was introduced in Java 1.0 and provided different approaches to work with time. The SimpleDateFormat inherits from DateFormat […]

  • 13 July

    Remove substring from String in Java

    Table of ContentsUsing String’s replace method to remove substring from String in JavaUsing String’s replaceFirst method to remove substring from String in JavaUsing String’s replaceAll method to remove substring from String in JavaUsing StringBuilder’s delete() method to remove substring from String in JavaUsing StringBuilder’s replace() method to remove substring from String in JavaConclusion In this […]

  • 9Cartoon
    13 July

    13 Best Working 9Cartoon Alternatives in 2021 (Tried and Tested)

    Table of ContentsBest 9cartoon AlternativesCartoonsOnAnimeDaoAnimeToonKissAnimeToonGetWatch Cartoons OnlineCartoonCrazyToonovaKimCartoonWatch SeriesNyaaToonJetKissCartoonFrequently Asked QuestionsWhat is 9cartoon?Is 9cartoon free?What happened to 9cartoon?Which are the best 9cartoon alternatives?Wrapping Up Are you having trouble accessing 9cartoon? Well then, you’re just at the right place. 9cartoon is a well-known web-based platform that bagged a large quality of cartoons, relative TV shows and movies. […]

  • 13 July

    Einthusan Alternatives : 16 Best websites like Enthusan in 2021

    Table of ContentsEinthusan alternativesYouTubeYuppTVSonyLIVJio CinemaHotstarVootZee5HungamaAmazon Prime VideoAirtel XtremeMX PlayerEros NowNetflixHonorable Mentions123 MoviesF MoviesSoap2dayFrequently Asked Questions**Is Einthusan Blocked in India?Is Einthusan Safe?Is Einthusan Free?Einthusan Downloader: Is it legit?Final Words Einthusan is a well-known platform for watching movies online. From streaming in different languages to downloading them for online viewing, the platform offered everything that movie lovers […]

  • CQATest
    13 July

    Everything You Need to Know About CQATest in 2021

    Table of ContentsCQATest: A Brief OverviewHow Can CQATest Help?Problems Associated with CQA TestFixing Problems Associated with CQATestDisabling CQATest AppMethod 1: Force Stopping CQATest AppMethod 2: Resetting Your DevicePrecautions: Things to Keep in Mind Before Disabling CQATest.FAQsWhat is CQATest on Android?What does CQA stand for?Is CQATest app a virus?Is CQA Test Safe?What are the most common […]

  • Copy DataFrame in Python
    10 July

    Copy DataFrame in Pandas

    This articles provide different ways to copy DataFrame in Pandas.

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.