• 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

Print all nodes that are at distance k from a leaf node

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

How Radix sort works

Find Percentage of Words matching in Two Strings

SAP Interview Questions

Minimum insertions to form a palindrome

Python Dictionaries

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

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

Microsoft BING Interview Experience

Get Minimum element in O(1) from input numbers or Stack

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Max Sum in circularly situated Values

K’th Largest Element in BST when modification to BST is not allowed

Printing each word reverse in string

Maximum occurred Smallest integer in n ranges

Maximum of all subarrays of size k

Find Nearest Minimum number in left side in O(n)

Apriori algorithm C Code Data Mining

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Find the smallest window in a string containing all characters of another string

Subset Sum Problem Dynamic programming

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Find the element that appears once others appears thrice

Right view of Binary tree

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

TicTacToe Game As Asked in Flipkart

Add Sub Multiply very large number stored as string

Knight Tour Problem (Graph – Breadth First Search)

Count Possible Decodings of a given Digit Sequence

Copyright © 2025 · Genesis Framework · WordPress · Log in