• 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

SAP Hiring Off-Campus General Aptitude

Maximum of all subarrays of size k

LeetCode : Word Search

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

The Magic HackerEarth Nirvana solutions Hiring Challenge

Hackerearth : Counting Subarrays

Maximum occurred Smallest integer in n ranges

Find next greater number with same set of digits

Find loop in Singly linked list

Regular Expression Matching

Count number of ways to reach a given score in a game

Max Sum in circularly situated Values

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

Longest Increasing Subsequence

Calculate price of parking from parking start end time prices

C++ OOPs Part1

Wrong Directions given find minimum moves so that he can reach to the destination

Number of Islands BFS/DFS

Binary Tree Isomorphic to each other

Code Chef PRGIFT Solution

Maximum difference between two elements s.t larger element appears after the smaller number

Sort Stack in place

Maximum size of square sub matrix with all 1’s in a binary matrix

Binary Tree in Java

System Design: Designing a LLD for Hotel Booking

C++ OOPs Part2

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

DFS (Depth First Search)

Given a string, find the first character which is non-repetitive

Printing intermediate Integers between one element & next element of array

Copyright © 2025 · Genesis Framework · WordPress · Log in