# Find Maximum Subarray Sum

Posted in

Vinay Khatri
Last updated on September 10, 2024

## Problem

The objective is to find the elements of a continuous subarray ``` nums ``` of integers that have the highest sum given an array.

## Brute force approach

The naïve method is to produce all possible subarrays and then display the subarray with the highest sum. This will take O(N2) time which is not efficient.

## Efficient approach

The aim is to utilise Kadane's Algorithm to discover the largest subarray sum, record the starting and ending indexes of the subarray with the highest sum, and then print the subarray from starting index to the ending index. The steps are as follows: Set the three variables ``` end ``` , ``` curr ``` , and ``` Max ``` to the first value in the input array.

Starting with index (say) 0, change curr to ``` max( ``` ``` nums [i], nums [i] + Max ``` ``` ) ``` and ``` Max ``` , and set end to ``` i ``` only if ``` curr > Max ``` . To get the start index, iterate from ``` end ``` to the left, decrementing the value of Max until it equals ``` 0 ``` . The start index is the point at which it becomes zero.

### C++ Programming

```#include <bits/stdc++.h>
using namespace std;
void maxSubarray(vector<int>& nums)
{
// Initialize curr and Max
int end, curr = nums[0];
int Max = nums[0];

// Iterate for all the elements for maximum sum
for (int i = 1; i < nums.size(); ++i)
{
curr = max(nums[i], nums[i] + curr);
// Check if curr is greater
// than Max
if (curr > Max)
{
Max = curr;
end = i;
}
}

int start = end;

// Traverse in left direction
while (start >= 0) {

Max -= nums[start];

if (Max == 0)
break;

// decrement the start index
start--;
}
for (int i = start;
i <= end; ++i) {

cout << nums[i] << " ";
}
}

int main()
{
vector<int> nums
= { 1, 2, 3, -4};
maxSubarray(nums);
}
```

Output

`1 2 3`

### Python Programming

```def maxSubarray(nums):

# Initialize curr and Max
curr = nums[0]
Max = nums[0]

# Iterate for all the elements
for i in range(1, len(nums)):
curr = max(nums[i], nums[i] + curr)

# Check if curr is greater
# than Max
if (curr > Max):
Max = curr
end = i

start = end

# Traverse in left direction
while (start >= 0):
Max -= nums[start]

if (Max == 0):
break

# Decrement the start index
start -= 1
for i in range(start, end + 1):
print(nums[i], end = " ")
arr = [1, 2, 4, -5]
maxSubarray(arr)```

Output

```1 2 4
```

### C# Programming

```using System;
using System.Collections.Generic;
class Solution{

static void maxSubarray(List<int> nums)
{
// Initialize curr and Max
int end = 0, curr = nums[0];
int Max = nums[0];

// Iterate for all the elements
for (int i = 1; i < nums.Count; ++i)
{
curr = Math.Max(nums[i], nums[i] + curr);
// Check if curr is greater
// than Max
if (curr > Max)
{
Max = curr;
end = i;
}
}

int start = end;

// Traverse in left direction
while (start >= 0)
{
Max -= nums[start];

if (Max == 0)
break;

// decrement the start index
start--;
}
for(int i = start; i <= end; ++i)
{
Console.Write(nums[i] + " ");
}
}

public static void Main(String[] args)
{
List<int> nums = new List<int>();
maxSubarray(nums);
}
}
```

Output

`1 2 -1 3`

People are also reading: