Size of subarray with max sum code in C++

April 13, 2023

Size of sub-array with max sum

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.

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.

Here’s an 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.

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

Algorithm:

Initialize max_sum to the smallest possible integer value, current_sum to 0, start to 0, and end to 0.
Iterate through the array from left to right, for each element: a. Compare the current sum current_sum plus the current element with the current element itself. If the former is greater, update current_sum to the sum, and update end to the current index. b. If the current element is greater, start a new sub-array with the current element as the starting element, update current_sum to the current element, and update both start and end to the current index.
Update max_sum if the current sum current_sum is greater.
After the iteration, the sub-array with the maximum sum is indicated by the start and end indices, and the size of the sub-array is end - start + 1. Return this value as the result.

Note The time complexity of above algorithm to find the maximum subarray sum and its size is O(n), where n is the size of the input array

C++ code for Size of sub-array with max sum

Run

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int maxSizeSubarrayWithMaxSum (vector<int> &nums)
{
  int max_sum = INT_MIN;
  int current_sum = 0;		// Initialize current_sum to 0
  int start = 0;		// Initialize start index to 0
  int end = 0;			// Initialize end index to 0

  for (int i = 0; i < nums.size (); i++)
    {
     
      if (current_sum + nums[i] < nums[i])
	{
	  current_sum = nums[i];
	  start = i;
	}
      else
	{
	  current_sum += nums[i];
	}

      // Update max_sum if current_sum is greater
      if (current_sum > max_sum)
	{
	  max_sum = current_sum;
	  end = i;
	}
    }

  // Size of subarray with max sum is end - start + 1
  return end - start + 1;
}

int main ()
{
  vector<int> nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
  int max_size = maxSizeSubarrayWithMaxSum (nums);
  cout << "Size of subarray with maximum sum: " << max_size << endl;
  return 0;
}

Output

Size of subarray with maximum sum: 4

Prime Course Trailer

Related Banners

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

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Tree in Data Structures (Introduction)
Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
Inorder Postorder PreOrder Traversals Examples
- Inorder Tree Traversal in Binary Tree: C | C++ | Java
- Preorder Tree Traversal in Binary Tree : C | C++ | Java
- Postorder Tree Traversal in Binary Tree : C | C++ | Java
Tree Traversal without Recursion
- Postorder Preorder Inorder Traversal without recursion
- Inorder Tree Traversal without Recursion – C | C++ | Java
- Preorder Tree Traversal without Recursion – C | C++ | Java
- Postorder Tree Traversal without Recursion – C | C++ | Java

Binary Search Trees

Binary search tree in Data Structures (Introduction)
- BST: Introduction to Binary Search Tree
- BST: Binary Search Tree Program : C | C++ | Java
- BST: Search a node in Binary Search Tree : C | C++ | Java
- BST: Insertion in a Binary Search Tree : C | C++ | Java
- BST: Deletion in a Binary Search Tree : C | C++ | Java

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

B-Tree
- B-Tree: Introduction
- B-Tree: Insertion : C | C++ | Java
- B-Tree: Deletion : C | C++ | Java

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