Size of subarray with max sum code in C++

May 21, 2025

Size of sub-array with max sum

Size of subarray with max sum code in C++ – Finding the size of a subarray with the maximum sum is a popular coding interview problem. It helps us understand how to work with arrays, loops, and logic. In this blog, we’ll learn what this problem means, understand it with an example, and solve it using different methods in C++, along with the code, output, and step-by-step algorithms.

Here, in this page we will discuss the program to find size of sub-array with max sum in C++ . We use Kadane’s algorithm, which runs in O(n) time.

The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. If current sum becomes 0 then at that point we also update the starting index.

Sum of continuous array

Size of sub-array with max sum in C++

The “Size of Sub-array with Maximum Sum” problem is a common algorithmic problem that involves finding the length or size of a contiguous sub-array within an array of integers, such that the sum of the sub-array is maximum among all possible sub-arrays. In other words, we need to find the sub-array with the largest sum.

Problem Statement:

You are given an array of integers (positive, negative, or zero). Your task is to find the maximum sum that can be obtained from any contiguous subarray, and also print the size (length) of that subarray.

Example:

Input: arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}

Output:
Maximum Sum = 6
Size of Subarray = 4

Explanation:

  • The subarray [4, -1, 2, 1] gives the maximum sum of 6 and has a length of 4.

Here’s another example to illustrate the problem:

  • Given an array of integers: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  • The subarray with the maximum sum is [4,-1,2,1], and the sum of this sub-array is 6. Thus, the size of the subarray with the maximum sum is 4.
  • The problem can be solved using efficient algorithms such as Kadane’s algorithm, which has a time complexity of O(N), where N is the size of the input array.
  • Kadane’s algorithm iterates through the array in a single pass, keeping track of the maximum sum of sub-arrays ending at each position of the array, and updating it as necessary.
Size of sub-array with max sum in C
Size of sub-array with max sum in C
DSA desktop gif
DSA mobile gif

Boyer-Moore’s Voting Algorithm

Majority Element in Array

Sort the array in Waveform

Segregate 0’s 1’s and 2’s in array

Maximum Average Sub-array of K length

Prime Course Trailer

Algorithm (General Steps) and Methods of Size of sub-array with max sum in C++

Algorithm:

  1. Start scanning the array.
  2. Keep a track of the current sum and maximum sum so far.
  3. Whenever the current sum becomes negative, reset it.
  4. Update the maximum sum if the current sum is greater.
  5. Track the start and end indexes to get the subarray size.

There are mainly 4 methods to for Size of sub-array with max sum in C++:

  • Method 1: Check All Possible Subarrays (Brute Force Way)
  • Method 2: Fastest Way to Find Max Sum (Kadane’s Algorithm)
  • Method 3: Show the Subarray That Gives the Max Sum
  • Method 4: Use a Table to Keep Track of Sums (Dynamic Programming)

Method 1 : Brute Force Approach

Algorithm:

  • Use two loops to consider every possible subarray.
  • Calculate the sum of each subarray.
  • Keep track of the maximum sum and its size.

Code:

Run

#include <iostream>
using namespace std;

int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int maxSum = arr[0], size = 1;

for(int i = 0; i < n; i++) {
int currSum = 0;
for(int j = i; j < n; j++) {
currSum += arr[j];
if(currSum > maxSum) {
maxSum = currSum;
size = j - i + 1;
}
}
}

cout << "Maximum Sum = " << maxSum << endl;
cout << "Size of Subarray = " << size << endl;

return 0;
}

Output:

Maximum Sum = 6 
Size of Subarray = 4

Method 2: Kadane’s Algorithm (Optimized)

Algorithm:

  • Initialize maxSum = arr[0] and currSum = 0.
  • Loop through each element:
    • Add the current element to currSum.
    • If currSum is more than maxSum, update maxSum and length.
    • If currSum becomes negative, reset it and start a new subarray.

Code:

Run

#include 
using namespace std;

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxSum = arr[0], currSum = 0;
    int start = 0, end = 0, tempStart = 0;

    for(int i = 0; i < n; i++) { currSum += arr[i]; if(currSum > maxSum) {
            maxSum = currSum;
            start = tempStart;
            end = i;
        }

        if(currSum < 0) {
            currSum = 0;
            tempStart = i + 1;
        }
    }

    int size = end - start + 1;
    cout << "Maximum Sum = " << maxSum << endl;
    cout << "Size of Subarray = " << size << endl;

    return 0;
}

Output:

Maximum Sum = 6 
Size of Subarray = 4

Method 3: Print the Largest Sum Subarray

This method is similar to Kadane’s, but we print the actual subarray too.

Code:

Run

#include 
using namespace std;

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxSum = arr[0], currSum = 0;
    int start = 0, end = 0, tempStart = 0;

    for(int i = 0; i < n; i++) { currSum += arr[i]; if(currSum > maxSum) {
            maxSum = currSum;
            start = tempStart;
            end = i;
        }

        if(currSum < 0) {
            currSum = 0;
            tempStart = i + 1;
        }
    }

    cout << "Maximum Sum = " << maxSum << endl;
    cout << "Subarray: ";
    for(int i = start; i <= end; i++) {
        cout << arr[i] << " ";
    }
    cout << "\nSize of Subarray = " << (end - start + 1) << endl;

    return 0;
}

Output:

Maximum Sum = 6 
Subarray: 4 -1 2 1 
Size of Subarray = 4

Method 4: Dynamic Programming Approach

In this approach, we maintain a dp array where dp[i] represents the maximum subarray sum ending at index i.

Algorithm:

  • Create dp[] array of size n.
  • Initialize dp[0] = arr[0], maxSum = dp[0].
  • For every i from 1 to n-1:
    • dp[i] = max(arr[i], arr[i] + dp[i-1])
    • Update maxSum accordingly.
  • Track the start and end index for size.

Code:

Run

#include 
#include 
using namespace std;

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    vector dp(n);
    dp[0] = arr[0];
    int maxSum = dp[0];
    int start = 0, end = 0, tempStart = 0;

    for(int i = 1; i < n; i++) { if(dp[i-1] > 0) {
            dp[i] = arr[i] + dp[i-1];
        } else {
            dp[i] = arr[i];
            tempStart = i;
        }

        if(dp[i] > maxSum) {
            maxSum = dp[i];
            start = tempStart;
            end = i;
        }
    }

    cout << "Maximum Sum = " << maxSum << endl;
    cout << "Size of Subarray = " << (end - start + 1) << endl;

    return 0;
}

Output:

Maximum Sum = 6 
Size of Subarray = 4

Conclusion

In this blog, we learned how to solve the problem of finding the size of the subarray with the maximum sum using different methods in C++.

  • The Brute Force method is simple but slow.
  • Kadane’s Algorithm is the most efficient and widely used approach.
  • You can also use Dynamic Programming if you want to keep track of all subarray sums.
  • We also learned how to print the actual subarray with the maximum sum.

This is a very common coding problem and a great way to improve your problem-solving skills in arrays and algorithms.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion : C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++ | Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
  • Find size of the Binary tree – C | C++ | Java
  • Find the height of binary tree – C | C++ | Java
  • Find maximum in binary tree – C | C++ | Java
  • Check whether two tree are identical- C| C++| Java
  • Spiral Order traversal of Tree- C | C++| Java
  • Level Order Traversal Line by Line – C | C++| Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- C| C++| Java
  • check whether tree is Symmetric – C| C++| Java.
  • Check for Children-Sum in Binary Tree- C|C++| Java
  • Sum of all nodes in Binary Tree- C | C++ | Java
  • Lowest Common Ancestor in Binary Tree- C | C++ | Java

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion :  C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++ | Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
  • Find size of the Binary tree – C | C++ | Java
  • Find the height of binary tree – C | C++ | Java
  • Find maximum in binary tree – C | C++ | Java
  • Check whether two tree are identical- C| C++| Java
  • Spiral Order traversal of Tree- C | C++| Java
  • Level Order Traversal LIne by Line – C | C++| Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- C| C++| Java
  • check whether tree is Symmetric  C| C++| Java.
  • Check for Children-Sum in Binary Tree- C|C++| Java
  • Sum of all nodes in Binary Tree- C | C++ | Java
  • Lowest Common Ancestor in Binary Tree. C | C++ | Java