# Largest Sum Contigous SubArray in C++ ## Largest Sum Contiguous Subarray in C++

Here, in this page we will discuss the program to find the largest sum contiguous subarray in C++. We will discuss two different ways in this page for finding such subarray.

## Largest Sum Contiguous Sub-Array in C++

The problem of finding the largest sum contiguous subarray in a given array involves identifying a subarray within the array that has the highest sum of its elements. This means we are searching for a continuous subarray in the given array that has the maximum possible sum.

For example, consider the following array:

```arr = [-2, -3, 4, -1, -2, 1, 5, -3]
```

The largest sum contiguous subarray in this array is [4, -1, -2, 1, 5], which has a sum of 7.

The problem of finding the largest sum contiguous subarray has a well-known algorithm called Kadane’s algorithm. The algorithm has a time complexity of O(n) and can be easily implemented in C++. ### Method Discussed :

• Method 1 : Brute Force Approach.
• Method 2 : Using Kadane’s Algorithm

### Method 1 :

• Declare a variable say res = INT_MIN.
• Run a loop from index 0 to n.
• Declare a variable sum = 0;
• Run a nested loop from index i to n.
• Set sum += arr[j].
• And res = max(res, sum)
• After Complete Iteration print res.

### Time and Space Complexity :

• Time Complexity : O(n2)
• Space Complexity : O(1)

### Method 1 : Code in C++

Run
```#include <bits/stdc++.h>
using namespace std;

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

int res = INT_MIN;

for(int i=0; i<n; i++){
int sum = 0;
for(int j=i; j<n; j++){
sum += arr[j];
res = max(sum, res);
}
}

cout<<res;
}

```

```7
```

### Method 2 :

• Create variable say max_sum that hold the required maximum sum of subarray and curr_sum and initialize max_sum with INT_MIN and curr_sum with 0.
• Now, iterate over the array, and for every ith value of the array, add it to curr_sum, and comapre it with max_sum like,
• if(max_sum < curr_sum) max_sum = curr_sum.
• Now, check if curr_sum <0 then set curr_sum to 0.
• After complete iteration we will get the result that store in max_sum variable.

### Time and Space Complexity :

• Time Complexity : O(n)
• Space Complexity : O(1)

### Method 2 : Code in C++

Run
```#include <bits/stdc++.h>
using namespace std;

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

int max_sum = INT_MIN, curr_sum =0;

for(int i=0; i< n; i++){

curr_sum += arr[i];

if(max_sum < curr_sum)
max_sum = curr_sum;

if(curr_sum < 0)
curr_sum = 0;

}

cout << max_sum;
}

```

```7
```

### 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

## Arrays

• Introduction to Arrays – CC++ | Java
• Introduction to 2-D Arrays – CC++ Java
• Sorting of Array – C | C++ | Java
• Array Rotation – CC++ | Java
• Reverse an array or string- CC++ | Java
• Find pairs in array with given sum – CC++ | Java
• Sort the array in Waveform – CC++ | Java
• Majority Element in Array – CC++ | Java
• Boyer-Moore’s Voting Algorithm – CC++ | Java
• K-pairs with smallest sum in 2 arrays – C | C++ | Java
• Largest Sum Contigous SubArray – CC++ | Java
• Maximum Average Sub-array of K length – CC++ | Java
• Size of sub-array with max sum – CC++ | Java
• Sub-array with given sum – CC++ | Java
• Triplet that sum to a given value – CC++ | Java
• Segregate 0’s and 1’s in array – CC++ | Java
• Segregate 0’s 1’s and 2’s in array – CC++ | Java
• Sort elements in array by frequency – CC++ | Java
• Finding pythagorean triplets in an array – CC++ | Java
• Reorder array using given indexes – CC++ | Java
• Merging two sorted arrays – CC++ | Java
• Minimum number of Merge Operations to make an Array Palindrome – CC++ | Java
• Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – CC++ | Java