Posted on by Kalkicode
Code Array

# Find max sum subarray in an array

The problem involves finding the contiguous subarray within a given array of integers that has the maximum sum. This is a well-known problem in the field of algorithms and has efficient solutions based on Kadane's algorithm.

## Problem Statement

Given an array of integers, find the contiguous subarray (containing at least one element) that has the largest sum and return the sum.

## Example

Consider the following array:

``arr = [2, 4, -2, -5, 6, -3, -2, 7, -2, 2]``

The contiguous subarray with the largest sum is `[6, -3, -2, 7, -2, 2]` or `[6, -3, -2, 7]`, and the sum of this subarray is `8`.

## Idea to Solve

Kadane's algorithm is a widely used technique to solve this problem efficiently in linear time. The idea behind this algorithm is to keep track of the maximum sum subarray ending at each position `i`. The maximum subarray sum ending at position `i` can be either the value at index `i` itself or the value at index `i` plus the maximum subarray sum ending at position `i-1`.

## Pseudocode

``````function largestSubarray(arr, size):
if size <= 0:
return

sum = arr[0]
result = arr[0]

for i from 1 to size - 1:
sum = max(sum + arr[i], arr[i])
result = max(sum, result)

print("Largest contiguous subarray sum:", result)

// Example usage
arr = [2, 4, -2, -5, 6, -3, -2, 7, -2, 2]
size = size(arr)
largestSubarray(arr, size)``````

## Algorithm Explanation

1. The `largestSubarray` function initializes the `sum` and `result` variables to the value of the first element in the array.
2. It iterates through the array from the second element to the last element.
3. At each step, the algorithm calculates the maximum sum subarray ending at position `i` by taking the maximum value between the value at index `i` itself and the value at index `i` plus the maximum sum subarray ending at position `i-1`.
4. The algorithm also keeps track of the maximum sum encountered so far in the `result` variable.
5. Finally, the algorithm prints the maximum sum of the contiguous subarray.

## Code Solution

``````// C Program
// Find largest sum of the contiguous subarray within an array
#include <stdio.h>

//Display elements of given array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("  %d", arr[i]);
}
printf("\n");
}
// Returns the maximum value of the given two integers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find the max sum Contiguous Subarray
void largestSubarray(int arr[], int size)
{
if (size <= 0)
{
return;
}
// Assign first element as result
int sum = arr[0];
int result = arr[0];
// Execute loop through by size
for (int i = 1; i < size; ++i)
{
sum = maxValue(sum + arr[i], arr[i]);
// Update the result
result = maxValue(sum, result);
}
// Display calculated result
printf(" Largest contiguous subarray sum : %d \n", result);
}
int main(int argc, char const *argv[])
{
// Define array of integer elements
int arr[] = {
2 , 4 , -2 , -5 , 6 , -3 , -2 , 7 , -2 , 2
};
// Get the size
int size = sizeof(arr) / sizeof(arr[0]);
printf("\n Array element \n");
printArray(arr, size);
largestSubarray(arr, size);
return 0;
}``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8``````
``````/*
Java Program for
Find largest sum of the contiguous subarray within an array
*/
class Subarray
{
//Display elements of given array
public void printArray(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("  " + arr[i]);
}
System.out.print("\n");
}
// Returns the maximum value of the given two integers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find the max sum Contiguous Subarray
public void largestSubarray(int[] arr, int size)
{
if (size <= 0)
{
return;
}
// Assign first element as result
int sum = arr[0];
int result = arr[0];
// Execute loop through by size
for (int i = 1; i < size; ++i)
{
sum = maxValue(sum + arr[i], arr[i]);
// Update the result
result = maxValue(sum, result);
}
// Display calculated result
System.out.print(" Largest contiguous subarray sum : " + result + " \n");
}
public static void main(String[] args)
{
// Define array of integer elements
int arr[] = {
2 , 4 , -2 , -5 , 6 , -3 , -2 , 7 , -2 , 2
};
// Get the size
int size = arr.length;
System.out.print("\n Array element \n");
}
}``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8
2  4  -2  -5  6  -3  -2  7  -2  2``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program for
Find largest sum of the contiguous subarray within an array
*/

class Subarray
{
public:
//Display elements of given array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << "  " << arr[i];
}
cout << "\n";
}
// Returns the maximum value of the given two integers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find the max sum Contiguous Subarray
void largestSubarray(int arr[], int size)
{
if (size <= 0)
{
return;
}
// Assign first element as result
int sum = arr[0];
int result = arr[0];
// Execute loop through by size
for (int i = 1; i < size; ++i)
{
sum = this->maxValue(sum + arr[i], arr[i]);
// Update the result
result = this->maxValue(sum, result);
}
// Display calculated result
cout << " Largest contiguous subarray sum : " << result << " \n";
}
};
int main()
{
// Define array of integer elements
int arr[] = {
2 , 4 , -2 , -5 , 6 , -3 , -2 , 7 , -2 , 2
};
// Get the size
int size = sizeof(arr) / sizeof(arr[0]);
cout << "\n Array element \n";
return 0;
}``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8
2  4  -2  -5  6  -3  -2  7  -2  2``````
``````// Include namespace system
using System;
/*
C# Program for
Find largest sum of the contiguous subarray within an array
*/
public class Subarray
{
//Display elements of given array
public void printArray(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write("  " + arr[i]);
}
Console.Write("\n");
}
// Returns the maximum value of the given two integers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find the max sum Contiguous Subarray
public void largestSubarray(int[] arr, int size)
{
if (size <= 0)
{
return;
}
// Assign first element as result
int sum = arr[0];
int result = arr[0];
// Execute loop through by size
for (int i = 1; i < size; ++i)
{
sum = maxValue(sum + arr[i], arr[i]);
// Update the result
result = maxValue(sum, result);
}
// Display calculated result
Console.Write(" Largest contiguous subarray sum : " + result + " \n");
}
public static void Main(String[] args)
{
// Define array of integer elements
int[] arr = {
2 , 4 , -2 , -5 , 6 , -3 , -2 , 7 , -2 , 2
};
// Get the size
int size = arr.Length;
Console.Write("\n Array element \n");
}
}``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8
2  4  -2  -5  6  -3  -2  7  -2  2``````
``````<?php
/*
Php Program for
Find largest sum of the contiguous subarray within an array
*/
class Subarray
{
//Display elements of given array
public	function printArray( & \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "  ". \$arr[\$i];
}
echo "\n";
}
// Returns the maximum value of the given two integers
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
else
{
return \$b;
}
}
// Find the max sum Contiguous Subarray
public	function largestSubarray( & \$arr, \$size)
{
if (\$size <= 0)
{
return;
}
// Assign first element as result
\$sum = \$arr[0];
\$result = \$arr[0];
// Execute loop through by size
for (\$i = 1; \$i < \$size; ++\$i)
{
\$sum = \$this->maxValue(\$sum + \$arr[\$i], \$arr[\$i]);
// Update the result
\$result = \$this->maxValue(\$sum, \$result);
}
// Display calculated result
echo " Largest contiguous subarray sum : ". \$result ." \n";
}
}

function main()
{
// Define array of integer elements
\$arr = array(2, 4, -2, -5, 6, -3, -2, 7, -2, 2);
// Get the size
\$size = count(\$arr);
echo "\n Array element \n";
}
main();``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8
2  4  -2  -5  6  -3  -2  7  -2  2``````
``````/*
Node Js Program for
Find largest sum of the contiguous subarray within an array
*/
class Subarray
{
//Display elements of given array
printArray(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + arr[i]);
}
process.stdout.write("\n");
}
// Returns the maximum value of the given two integers
maxValue(a, b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find the max sum Contiguous Subarray
largestSubarray(arr, size)
{
if (size <= 0)
{
return;
}
// Assign first element as result
var sum = arr[0];
var result = arr[0];
// Execute loop through by size
for (var i = 1; i < size; ++i)
{
sum = this.maxValue(sum + arr[i], arr[i]);
// Update the result
result = this.maxValue(sum, result);
}
// Display calculated result
process.stdout.write(" Largest contiguous subarray sum : " + result + " \n");
}
}

function main()
{
// Define array of integer elements
var arr = [2, 4, -2, -5, 6, -3, -2, 7, -2, 2];
// Get the size
var size = arr.length;
process.stdout.write("\n Array element \n");
}
main();``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8
2  4  -2  -5  6  -3  -2  7  -2  2``````
``````#   Python 3 Program for
#   Find largest sum of the contiguous subarray within an array

class Subarray :
# Display elements of given array
def printArray(self, arr, size) :
i = 0
while (i < size) :
print("  ", arr[i], end = "")
i += 1

print(end = "\n")

#  Returns the maximum value of the given two integers
def maxValue(self, a, b) :
if (a > b) :
return a
else :
return b

#  Find the max sum Contiguous Subarray
def largestSubarray(self, arr, size) :
if (size <= 0) :
return

#  Assign first element as result
sum = arr[0]
result = arr[0]
i = 1
#  Execute loop through by size
while (i < size) :
sum = self.maxValue(sum + arr[i], arr[i])
#  Update the result
result = self.maxValue(sum, result)
i += 1

#  Display calculated result
print(" Largest contiguous subarray sum : ", result ," ")

def main() :
#  Define array of integer elements
arr = [2, 4, -2, -5, 6, -3, -2, 7, -2, 2]
#  Get the size
size = len(arr)
print("\n Array element ")

if __name__ == "__main__": main()``````

#### Output

`````` Array element
2   4   -2   -5   6   -3   -2   7   -2   2
Largest contiguous subarray sum :  8
2   4   -2   -5   6   -3   -2   7   -2   2``````
``````#   Ruby Program for
#   Find largest sum of the contiguous subarray within an array

class Subarray
# Display elements of given array
def printArray(arr, size)
i = 0
while (i < size)
print("  ", arr[i])
i += 1
end

print("\n")
end

#  Returns the maximum value of the given two integers
def maxValue(a, b)
if (a > b)
return a
else
return b
end

end

#  Find the max sum Contiguous Subarray
def largestSubarray(arr, size)
if (size <= 0)
return
end

#  Assign first element as result
sum = arr[0]
result = arr[0]
i = 1
#  Execute loop through by size
while (i < size)
sum = self.maxValue(sum + arr[i], arr[i])
#  Update the result
result = self.maxValue(sum, result)
i += 1
end

#  Display calculated result
print(" Largest contiguous subarray sum : ", result ," \n")
end

end

def main()
#  Define array of integer elements
arr = [2, 4, -2, -5, 6, -3, -2, 7, -2, 2]
#  Get the size
size = arr.length
print("\n Array element \n")
end

main()``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8
2  4  -2  -5  6  -3  -2  7  -2  2
``````
``````/*
Scala Program for
Find largest sum of the contiguous subarray within an array
*/
class Subarray
{
//Display elements of given array
def printArray(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("  " + arr(i));
i += 1;
}
print("\n");
}
// Returns the maximum value of the given two integers
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find the max sum Contiguous Subarray
def largestSubarray(arr: Array[Int], size: Int): Unit = {
if (size <= 0)
{
return;
}
// Assign first element as result
var sum: Int = arr(0);
var result: Int = arr(0);
var i: Int = 1;
// Execute loop through by size
while (i < size)
{
sum = this.maxValue(sum + arr(i), arr(i));
// Update the result
result = this.maxValue(sum, result);
i += 1;
}
// Display calculated result
print(" Largest contiguous subarray sum : " + result + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subarray = new Subarray();
// Define array of integer elements
var arr: Array[Int] = Array(2, 4, -2, -5, 6, -3, -2, 7, -2, 2);
// Get the size
var size: Int = arr.length;
print("\n Array element \n");
}
}``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8
2  4  -2  -5  6  -3  -2  7  -2  2``````
``````/*
Swift 4 Program for
Find largest sum of the contiguous subarray within an array
*/
class Subarray
{
//Display elements of given array
func printArray(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("  ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Returns the maximum value of the given two integers
func maxValue(_ a: Int, _ b: Int)->Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find the max sum Contiguous Subarray
func largestSubarray(_ arr: [Int], _ size: Int)
{
if (size <= 0)
{
return;
}
// Assign first element as result
var sum: Int = arr[0];
var result: Int = arr[0];
var i: Int = 1;
// Execute loop through by size
while (i < size)
{
sum = self.maxValue(sum + arr[i], arr[i]);
// Update the result
result = self.maxValue(sum, result);
i += 1;
}
// Display calculated result
print(" Largest contiguous subarray sum : ", result ," ");
}
}
func main()
{
// Define array of integer elements
let arr: [Int] = [2, 4, -2, -5, 6, -3, -2, 7, -2, 2];
// Get the size
let size: Int = arr.count;
print("\n Array element ");
}
main();``````

#### Output

`````` Array element
2   4   -2   -5   6   -3   -2   7   -2   2
Largest contiguous subarray sum :  8
2   4   -2   -5   6   -3   -2   7   -2   2``````
``````/*
Kotlin Program for
Find largest sum of the contiguous subarray within an array
*/
class Subarray
{
//Display elements of given array
fun printArray(arr: Array < Int > , size: Int): Unit
{
var i: Int = 0;
while (i < size)
{
print("  " + arr[i]);
i += 1;
}
print("\n");
}
// Returns the maximum value of the given two integers
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find the max sum Contiguous Subarray
fun largestSubarray(arr: Array < Int > , size: Int): Unit
{
if (size <= 0)
{
return;
}
// Assign first element as result
var sum: Int = arr[0];
var result: Int = arr[0];
var i: Int = 1;
// Execute loop through by size
while (i < size)
{
sum = this.maxValue(sum + arr[i], arr[i]);
// Update the result
result = this.maxValue(sum, result);
i += 1;
}
// Display calculated result
print(" Largest contiguous subarray sum : " + result + " \n");
}
}
fun main(args: Array < String > ): Unit
{
// Define array of integer elements
var arr: Array < Int > = arrayOf(2, 4, -2, -5, 6, -3, -2, 7, -2, 2);
// Get the size
var size: Int = arr.count();
print("\n Array element \n");
}``````

#### Output

`````` Array element
2  4  -2  -5  6  -3  -2  7  -2  2
Largest contiguous subarray sum : 8
2  4  -2  -5  6  -3  -2  7  -2  2``````

## Time Complexity

The algorithm iterates through the array once, performing constant time operations at each step. Therefore, the time complexity is linear, `O(n)`, where `n` is the size of the array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post