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

  • Compare date in SQL
    08 October

    How to Compare Dates in SQL

    Table of ContentsAgendaIntroduction to DATE in SQLComparing Dates in SQL with ExamplesUsing Comparison OperatorsUsing the BETWEEN ClauseComparing Dates for DATETIME Datatypes/FormatsUsing Comparison Operator with TimeStampCasting DATETIME as DATE without TimestampUsing Between Clause with DATETIME Agenda This article will look at yet another interesting topic in SQL commonly asked in interviews – How to Compare Dates […]

  • Get Number of Elements in Array in C++
    08 October

    Get Number of Elements in Array in C++

    Table of ContentsGet Number of Elements in Array in C++Using the sizeof() functionUsing the pointersUsing the size() functionGet the frequency of each element in array in C++Using nested for loopUsing maps One of the most fundamental collections in any programming language is an array. It stores a similar type of data at specific indices that […]

  • can you screenshot onlyfans
    08 October

    Can You Screenshot OnlyFans? Here is Everything You Need to Know

    Table of ContentsOnlyFans: A Brief IdeaCan You Screenshot OnlyFans?Can You Screenshot OnlyFans Without Getting Banned?Can You Screenshot OnlyFans Without Them Knowing: Screenshot NotificationsFrequently Asked Questions About: Can You Screenshot OnlyFans?What Happens When You Try Taking OnlyFans Screenshots?Is Screenshotting Illegal?Do the OnlyFans screenshots lead to a permanent account ban?Can OnlyFans screenshots be detected?Wrapping Up Can you […]

  • Trust browser enable
    08 October

    How to enable trust wallet browser

    Table of ContentsTrust DApp Browser: A Brief OverviewWhat are DApps on Trust Wallet?Access DApps Using Trust Wallet: Easiest ApproachTrust Browser Enable on Android: How to Activate/Enable DApp Browser on Trust WalletTrust Browser Enable on iOS: How to Activate/Enable DApp Browser on Trust Wallet#Method 1: “Trust Browser Enable” Procedure#Method 2: Enabling DApp by Visiting Pancake SwapFrequently […]

  • how-to-find-someone-on-onlyfans
    07 October

    How to Find Someone on OnlyFans: Working Methods

    Table of ContentsHow to Find Someone on OnlyFansHow to Find Someone on OnlyFansHow to Find Someone on OnlyFans: The Official Username MethodThe OnlyFans TrickHow to Find Someone on OnlyFans: The Email MethodHow to Find Someone on OnlyFans: The OnlyFinder MethodHow to Find Someone on OnlyFans By Location (Map Feature)How to Find Someone on OnlyFans By […]

  • How to delete snapchat messages the other person saved
    07 October

    How to delete snapchat messages the other person saved

    Table of ContentsHow to delete Snapchat messages the other person saved#Step 1: Log in to Your Snapchat Account#Step 2: Navigate to the Desired Chat#Step 3: Unsave The Message from Your End#Step 4: Long-Press and Delete the Message#Step 5: Proceed with the Learn More option#Step 6: Click Okay#Step 7: Tap on the option that says “Delete.”How […]

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.