Maximum Subarray Problem
Finding the Maximum Subarray Sum
The Maximum Subarray Problem is a classic algorithmic challenge that frequently appears in coding interviews and real-world applications. The goal is to identify the contiguous subarray within a given array of integers that has the largest sum.
This article provides a clear and efficient approach to solve the problem using Kadane’s Algorithm.
Problem Description
Given an array of integers, nums, the task is to find the largest sum of any contiguous subarray within the array.
Key Points:
- A subarray is a sequence of consecutive elements within the array.
- The solution should work efficiently even for larger arrays.
Explanation:
The subarray [4,-2,2,1,-1,4] has the largest sum 8.
Constraints:
- 1 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
Optimized Solution: Kadane’s Algorithm
Kadane’s Algorithm provides an elegant and efficient way to solve this problem with a linear time complexity of O(n). It works by iterating through the array and maintaining two values:
- Current Sum (
current_sum): The maximum sum of the subarray ending at the current index. - Global Maximum (
max_sum): The maximum sum encountered so far.
Steps of the Algorithm:
- Initialize
current_sumas0andmax_sumas negative infinity. - Iterate through each element in the array:
- Add the current element to
current_sum. - If
current_sumbecomes less than the current element, resetcurrent_sumto the current element. This is equivalent to starting a new subarray. - Update
max_sumifcurrent_sumexceeds it.
- Add the current element to
- Return
max_sum.
Challenges in Multiplying Strings
Handling Large Numbers:
Since the strings can be up to 200 digits long, directly converting them to integers is not feasible due to potential overflow or performance issues.Simulating Manual Multiplication:
Multiplication needs to be performed at the digit level, just like how we multiply numbers by hand on paper.Efficient Result Construction:
Managing intermediate results and carrying over values without excessive computational overhead can be tricky.
There are mainly 2 approach to solve this problem –
- Brute Force
- Recursion Method
1. Brute Force
- Time complexity: O(n^2)
- Space complexity: O(1)
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
if (num1.size() < num2.size()) { return multiply(num2, num1); } string res = ""; int zero = 0; for (int i = num2.size() - 1; i >= 0; --i) {
string cur = mul(num1, num2[i], zero);
res = add(res, cur);
zero++;
}
return res;
}
string mul(string s, char d, int zero) {
int i = s.size() - 1, carry = 0;
int digit = d - '0';
string cur;
while (i >= 0 || carry) {
int n = (i >= 0) ? s[i] - '0' : 0;
int prod = n * digit + carry;
cur.push_back((prod % 10) + '0');
carry = prod / 10;
i--;
}
reverse(cur.begin(), cur.end());
return cur + string(zero, '0');
}
string add(string num1, string num2) {
int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
string res;
while (i >= 0 || j >= 0 || carry) {
int n1 = (i >= 0) ? num1[i] - '0' : 0;
int n2 = (j >= 0) ? num2[j] - '0' : 0;
int total = n1 + n2 + carry;
res.push_back((total % 10) + '0');
carry = total / 10;
i--;
j--;
}
reverse(res.begin(), res.end());
return res;
}
};public class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length, res = nums[0];
for (int i = 0; i < n; i++) {
int cur = 0;
for (int j = i; j < n; j++) {
cur += nums[j];
res = Math.max(res, cur);
}
}
return res;
}
}class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n, res = len(nums), nums[0]
for i in range(n):
cur = 0
for j in range(i, n):
cur += nums[j]
res = max(res, cur)
return resclass Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxSubArray(nums) {
let n = nums.length, res = nums[0];
for (let i = 0; i < n; i++) {
let cur = 0;
for (let j = i; j < n; j++) {
cur += nums[j];
res = Math.max(res, cur);
}
}
return res;
}
}2. Recursion
Time & Space Complexity
- Time complexity: O(2^n)
- Space complexity: O(n)
Where m is the length of the array queries and n is the length of the array intervals.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return dfs(nums, 0, false);
}
private:
int dfs(vector<int>& nums, int i, bool flag) {
if (i == nums.size()) return flag ? 0 : -1e6;
if (flag) return max(0, nums[i] + dfs(nums, i + 1, true));
return max(dfs(nums, i + 1, false),
nums[i] + dfs(nums, i + 1, true));
}
};public class Solution {
public int maxSubArray(int[] nums) {
return dfs(nums, 0, false);
}
private int dfs(int[] nums, int i, boolean flag) {
if (i == nums.length) {
return flag ? 0 : (int) -1e6;
}
if (flag) {
return Math.max(0, nums[i] + dfs(nums, i + 1, true));
}
return Math.max(dfs(nums, i + 1, false),
nums[i] + dfs(nums, i + 1, true));
}
}class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def dfs(i, flag):
if i == len(nums):
return 0 if flag else -1e6
if flag:
return max(0, nums[i] + dfs(i + 1, True))
return max(dfs(i + 1, False), nums[i] + dfs(i + 1, True))
return dfs(0, False)class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxSubArray(nums) {
const dfs = (i, flag) => {
if (i === nums.length) return flag ? 0 : -1e6;
if (flag) return Math.max(0, nums[i] + dfs(i + 1, true));
return Math.max(dfs(i + 1, false),
nums[i] + dfs(i + 1, true));
};
return dfs(0, false);
}
}
