• 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

Linked List V/S Binary Search Tree

Hackerearth : Counting Subarrays

CodeChef’ RRCOPY

LeetCode: Container With Most Water

Possible sizes of bus to carry n groups of friends

Connect n ropes with minimum cost

Common Ancestor in a Binary Tree or Binary Search Tree

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

C++ OOPs Part2

Given Set of words or A String find whether chain is possible from these words or not

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

System Design: Designing a LLD for Hotel Booking

Spanning Tree

25 horses 5 tracks Find 3 fastest puzzle

Python Dictionaries

Templates in C++

Naurki.com Security Breach

FizzBuzz Solution C C++

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Binary Tree in Java

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

Find min element in Sorted Rotated Array (With Duplicates)

VMWare SDEII Interview

Daughter’s Age VeryGood Puzzle

Memory Efficient LinkedList

Word Break Problem

Count Possible Decodings of a given Digit Sequence

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

BlueStone E-commerce Interview Experience

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

Copyright © 2023 · Genesis Framework · WordPress · Log in