Size of subarray with max sum code in C++
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.
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.
Algorithm (General Steps) and Methods of Size of sub-array with max sum in C++
Algorithm:
- Start scanning the array.
- Keep a track of the current sum and maximum sum so far.
- Whenever the current sum becomes negative, reset it.
- Update the maximum sum if the current sum is greater.
- 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:
#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:
#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:
#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:
#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 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
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
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
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 Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
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
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
Login/Signup to comment