• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Maximum sum contiguous subarray of an Array

December 25, 2017 by Dhaval Dave

Given an Array A with n integers both positive and negative, find the maximum sum contiguous subarray within A which has the largest sum

Naive Approach –

You can find the sum of all subarrays present in the array and determine the maximum among them. This approach will run in O(n2) time complexity.

Below is the implementation of above idea in C++ :

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;

    int A[n];
    for(int i=0;i<n;i++) 
    cin>>A[i];
 
    long long max_ans;
    max_ans=A[0];

    for(int i=0;i<n;i++)
    {
        long long result=0;
        for(int j=i;j<n;j++)
        {
            result+=A[j];
            max_ans=max(max_ans,result);
        }
    }
 
    cout<<max_ans;
    return 0;
}

 

Efficient Method to find Maximum Sum Contiguous subarray:

Kadane’s algorithm finds the maximum sum subarray in O(n) time complexity which involves finding the maximum sum subarray possible ending at each indexes. This algorithm is a very simple application of dynamic programming i.e. it uses the previously calculated values to find the next value which is to be calculated. Basically this algorithm calculates two values the maximum sum until the current index and the maximum sum so far. Each time we iterate we compare and update these two variables. We get the maximum sum subarray after we traverse the array once.

Initially store A[0] in curr_max and overall_max variables since it is the maximum we can have when we have only the first element. For index 1 we find the maximum between A[1] and (curr_max + A[1]). Thus if the element at index 1 is greater than the sum of subarray [0,1] it will be updated as the curr_max or else the subarray [0,1] will be the current maximum sum ending at that index. In the next iteration we will again find the maximum between the current element and the maximum sum subarray that we had calculated before, so it is guaranteed that we will have the maximum subarray sum with us if we had i elements. While doing so we also update the variable overall_max, which essentially just finds out the maximum of all the curr_max values of all i. Thus after traversing the whole array we have the maximum sum of a contiguous subarray stored in overall_max.

Algorithm:

Initialize variables:
overall_max=A[0];
curr_max=A[0];

Iterate over the Array A:
{
  Update curr_max with the maximum of (A[i]) and (curr_max + A[i]);
  Update overall_max with the maximum of (curr_max) and (overall_max);
}

 

Below is the implementation of the above algorithm in C++:

#include<bits/stdc++.h>
using namespace std;
 
long long KadaneMaxSumSubarray(long long A[],int size)
{
    long long overall_max = A[0];
    long long curr_max = A[0];
 
    for (int i=1;i<size;i++) 
    { 
        curr_max = max(A[i],curr_max + A[i]);
        overall_max = max(overall_max, curr_max);
    } 
    return overall_max;
} 

int main()
{ 
    int n;
    cin>>n;
 
    long long A[n];
    for(int i=0;i<n;i++)
    cin>>A[i];
 
    long long max_sum=KadaneMaxSumSubarray(A,n);
    cout<<max_sum;
    return 0;
}

Similar Articles

Filed Under: Algorithm, Array, Interview Experience, Interview Questions, problem Tagged With: Array, Dynamic Programming, Kadane

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

VMWare Openings

Singly linked list

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Urban Ladder Written Test.

The Magic HackerEarth Nirvana solutions Hiring Challenge

Daughter’s Age VeryGood Puzzle

Sequence Finder Dynamic Programming

SAP Off Campus Hiring_ March 2015 Verbal Skills

Diagonal Traversal of Binary Tree

Find position of the only set bit

FizzBuzz Solution C C++

Count Possible Decodings of a given Digit Sequence

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Longest Increasing Subsequence

Search element in a matrix with all rows and columns in sorted order

Edit Distance ( Dynamic Programming )

Practo Hiring Experience

Adobe Interview Questions 8 month Exp

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Printing Longest Common Subsequence

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

Python Dictionaries

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Binary Tree in Java

HackeEarth Flipkart’s Drone

Client Server C program

Closed Parentheses checker

Minimum insertions to form a palindrome

Find two non repeating elements in an array of repeating elements

How strtok() Works

Copyright © 2025 · Genesis Framework · WordPress · Log in