Table of Contents

## Problem Statement

You are given an array of integers. The problem statement asks to find out the largest sum contiguous subarray. This means nothing but to find a subarray (continuous elements) which has the largest sum among all other subarrays in the given array.

## Example

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

[2, 4]

Explanation: The sub-array starting from index 2 to index 4 has the largest sum of 7 within the array. Any other subarray will give a sum smaller than 7.

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

[2, 6]

Explanation: The sub-array starting from index 2 to index 6 has the largest sum of 10 within the array.

## Algorithm for Largest Sum Contiguous Subarray Problem

1. Set the maxValue to the minimum value an integer can hold (INT_MIN / Integer.MIN_VALUE) and maxPoint to 0. 2. Set start, end, s to 0. 3. Traverse the array starting from i=0 to i<size(length of the array). 1. Add the maxPoint and arr[i] and update it into the maxPoint. 2. Check if maxValue is less than maxPoint, then update the following: 1. maxValue = maxPoint 2. start=s 3. end=i 3. Check if the maxPoint is less than 0, then update 1. maxPoint=0 2. s=i+1 4. Print ‘start’ and ‘end’ as an index and the maxValue as the largest sum.

### Explanation

We have given an array of integers. We have asked to find out the largest sum contiguous subarray. It can contain negative and positive integers as well. We have to handle all those cases. For this, we are going to traverse the array just for once and hence it has the time of complexity of **O(n)**. We will find the maximum contiguous subarray sum in linear time complexity.

Set up some values, like **maxValue** to the minimum value an Integer can hold, **maxPoint** to 0, and **start**, **end**, and **s** to 0. Start traversing the array up to the length **n**. Add the current array element into the sum maxPoint. Store it into the maxPoint, every time value of **i **increments in the loop, we do this operation. We have already fixed the value of **maxValue** to the minimum value of an Integer and check if maxValue is less than maxPoint. If this is true then we are going to update the value of maxValue from maxPoint, start to s. This start variable will set up the value of the starting range of contiguous sub-array and we have an end, which we update with i (loop variable).

We will check now if **maxPoint** is less than 0, means the addition of array values until now is negative. Then we again update the value of maxPoint to 0 and s to i+1. This **s** will help us again in setting up the value of starting range and help us find out the largest sum subarray. This maxPoint we will be initialized to zero because we have to find out the largest sum and then we are going to print the value of start and end as a starting and ending indicess of required largest sum sub-array. If we use this approach we can find the largest sum contiguous subarray in a single pass.

## Code for Largest Sum Contiguous Subarray Problem

### C++ Code

#include<bits/stdc++.h> using namespace std; // This Function prints the Largest Sum Contiguous Subarray void getLargestSumContiguousSubarray(int arr[], int size) { // initialising variables with starting values int maxValue = INT_MIN; int maxPoint = 0; int start =0, end = 0, s=0; for (int i=0; i< size; i++ ) { maxPoint += arr[i]; if (maxValue < maxPoint) { maxValue = maxPoint; start = s; end = i; } if (maxPoint < 0) { maxPoint = 0; s = i + 1; } } cout << "Sub-Array starting from "<< start<< " to "<< end<< " has a largest sum of " <<maxValue; } int main() { int arr[] = {1, -3, 4, -2, 5, -6, 2}; int n = sizeof(arr)/sizeof(arr[0]); getLargestSumContiguousSubarray(arr, n); return 0; }

Sub-Array starting from 2 to 4 has a largest sum of 7

### Java Code

class LargestSumSubArray { // This Function prints Largest Sum Contiguous Subarray public static void getLargestSumContiguousSubarray(int arr[], int size) { // initialising variables with starting values int maxValue = Integer.MIN_VALUE; int maxPoint = 0; int start =0, end = 0, s=0; for (int i=0; i< size; i++ ) { maxPoint += arr[i]; if (maxValue < maxPoint) { maxValue = maxPoint; start = s; end = i; } if (maxPoint < 0) { maxPoint = 0; s = i + 1; } } System.out.println("Sub-Array starting from "+ start + " to "+ end + " has a largest sum of " + maxValue); } public static void main(String [] args) { int arr[] = {1, -3, 4, -2, 5, -6, 2}; int n = arr.length; getLargestSumContiguousSubarray(arr, n); } }

Sub-Array starting from 2 to 4 has a largest sum of 7

## Complexity Analysis

### Time Complexity

Since we are running a single loop over the input array of size n. Thus algorithm for the largest sum contiguous subarray has linear time complexity. **O(n) **where **“n” **is the number of elements in the array.

### Space Complexity

We have used a single 1D input array for storing the integers. Thus contributing a linear space complexity to Largest Sum Contiguous Subarray Problem. **O(n) **where **“n” **is the number of elements in the array.