.png)
Find the Largest Sum Contiguous Subarray
Problem Statement
Given an array of integers (which may include negative numbers), find the maximum sum of a contiguous subarray.
A contiguous subarray is a sequence of elements that appear consecutively in the array.
This problem is commonly known as the Maximum Subarray Problem.
Example 1
Input
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
Output
7
Explanation
The subarray [4, -1, -2, 1, 5] has the largest sum:
4 + (-1) + (-2) + 1 + 5 = 7
Example 2
Input
arr = [1, 2, 3, 4]
Output
10
Why This Problem Is Important
This is one of the most important array problems because it:
- Is a classic interview question
- Tests understanding of:
- Subarrays vs subsequences
- Dynamic decision making
- Introduces Kadane’s Algorithm
- Appears in:
- Competitive programming
- System design optimizations
- Financial and data analysis problems
Approaches to Solve the Problem
- Brute Force Approach
- Optimized Approach – Kadane’s Algorithm
Approach 1: Brute Force Method
Idea
- Generate all possible subarrays
- Calculate the sum of each subarray
- Track the maximum sum found
Algorithm
- Initialize maxSum with the smallest possible value
- Use two nested loops:
- First loop for starting index
- Second loop for ending index
- Calculate subarray sums
- Update maxSum whenever a larger sum is found
Time and Space Complexity
- Time Complexity: O(n²)
- Space Complexity: O(1)
C Implementation (Brute Force)
#include<stdio.h>
#include<limits.h>
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = 8;
int maxSum = INT_MIN;
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;
}
}
printf("Maximum Subarray Sum: %d", maxSum);
return 0;
}
Output
Maximum Subarray Sum: 7
Approach 2: Kadane’s Algorithm (Efficient Method)
Idea
- Traverse the array once
- Keep track of:
- currentSum: maximum sum ending at current index
- maxSum: overall maximum sum found so far
- If currentSum becomes negative, reset it to 0
Algorithm
- Initialize:
- currentSum = 0
- maxSum = -∞
- Traverse the array:
- Add current element to currentSum
- Update maxSum
- If currentSum < 0, reset it to 0
- maxSum holds the final answer
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
C++ Implementation (Kadane’s Algorithm)
#include <iostream>
#include <climits>
using namespace std;
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = 8;
int currentSum = 0;
int maxSum = INT_MIN;
for(int i = 0; i < n; i++) {
currentSum += arr[i];
if(currentSum > maxSum)
maxSum = currentSum;
if(currentSum < 0)
currentSum = 0;
}
cout << "Maximum Subarray Sum: " << maxSum;
return 0;
}
Output
Maximum Subarray Sum: 7
Java Implementation
public class KadaneAlgorithm {
public static void main(String[] args) {
int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
int currentSum = 0;
int maxSum = Integer.MIN_VALUE;
for (int x : arr) {
currentSum += x;
maxSum = Math.max(maxSum, currentSum);
if (currentSum < 0)
currentSum = 0;
}
System.out.println("Maximum Subarray Sum: " + maxSum);
}
}
Output
Maximum Subarray Sum: 7
Python Implementation
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
current_sum = 0
max_sum = float('-inf')
for x in arr:
current_sum += x
max_sum = max(max_sum, current_sum)
if current_sum < 0:
current_sum = 0
print("Maximum Subarray Sum:", max_sum)
Output
Maximum Subarray Sum: 7
JavaScript Implementation
let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
let currentSum = 0;
let maxSum = -Infinity;
for (let x of arr) {
currentSum += x;
maxSum = Math.max(maxSum, currentSum);
if (currentSum < 0)
currentSum = 0;
}
console.log("Maximum Subarray Sum:", maxSum);
Output
Maximum Subarray Sum: 7
Dry Run (Kadane’s Algorithm)
| Element | currentSum | maxSum |
|---|---|---|
| -2 | -2 → 0 | -2 |
| -3 | -3 → 0 | -2 |
| 4 | 4 | 4 |
| -1 | 3 | 4 |
| -2 | 1 | 4 |
| 1 | 2 | 4 |
| 5 | 7 | 7 |
| -3 | 4 | 7 |
Summary
- Kadane’s Algorithm solves the problem in linear time
- Works efficiently even with negative numbers
- One of the most important array algorithms
Key Takeaways
- Best Time Complexity: O(n)0
- Space Complexity: O(1)
- Foundation for advanced dynamic programming problems
Next Problem in the Series
Kadane’s Algorithm (Maximum Subarray Sum)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
