You are given an array 'arr' of length 'n', consisting of integers.
A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning and 0 or more integers from the end of an array.
Find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.
The sum of an empty subarray is 0.
Input: 'arr' = [1, 2, 7, -4, 3, 2, -10, 9, 1]
Output: 11
Explanation: The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].
The first line of input contains an integer 'n', representing the array's length.
The second line of input contains 'n' single space-separated integers, denoting the elements of the array.
The output contains the maximum subarray sum.
You do not need to print anything; it has already been taken care of. Just implement the given function.
9
1 2 7 -4 3 2 -10 9 1
11
The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].
6
10 20 -30 40 -50 60
60
3
-3 -5 -6
0
The expected time complexity is O(n).
1 <= 'n' <= 10 ^ 6
-10 ^ 6 <= 'arr[i]' <= 10 ^ 6
Time limit: 1sec
Using basic implementation, let’s check for all subarrays to find the maximum sum among them.
Let us check for all possible subarrays of the array. For this, we run two loops, where the outer loop points to the left boundary and the inner loop points to the outer boundary of the subarray.
Using another loop inside, find the sum of this subarray. Compare it with the maximum subarray sum obtained so far. After checking all the subarrays, simply return the maximum sum found.
O(n ^ 3), where ‘n’ is the length of the array.
There are n * (n + 1) / 2 subarrays in total, and for each subarray, we find its sum in O(n) time.
O(1), as constant extra space is required.
All tags
Sort by
Interview problems
JAVA || All Test Cases Passed || Easy Code
import java.util.* ;
import java.io.*;
public class Solution {
public static long maxSubarraySum(int[] arr, int n) {
// write your code here
long max = Integer.MIN_VALUE, sum = 0;
for (int i=0; i < n; i++ ){
sum += arr[i];
max = Math.max(max,sum);
if(sum < 0) sum = 0;
}
return max < 0 ? 0 : max;
}
}
Interview problems
Kadane 's Algorithm in java
import java.util.* ;
import java.io.*;
public class Solution {
public static long maxSubarraySum(int[] arr, int n) {
// write your code here
long maxSum = Integer.MIN_VALUE;
long currSum = 0;
for(int i = 0;i<n;i++){
currSum = currSum + arr[i];
if(currSum<0){
currSum = 0;
}
maxSum = Math.max(currSum,maxSum);
}
return maxSum;
}
}
Interview problems
Maximum Subarray Sum below code is correct or not if not provide ans
import java.util.* ;
import java.io.*;
public class Solution {
public static long maxSubarraySum(int[] arr, int n) {
long max=arr[0],sum=0;
for(int num:arr)
{ if(sum<=0){
sum=0;
}
sum+=num;
max=Math.max(sum,max);
}
return max;
}
}
Interview problems
Very EASY CPP APPROACH 0(1) ☄️
long long maxSubarraySum(vector<int> arr, int n) {
long long sum = 0;
long long maxi = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum > maxi)
maxi = sum;
if (sum < 0)
sum = 0;
}
return maxi;
}
Interview problems
Mechanical Maintenance Engineer
MECHANICAL MAINTENANCE RELATED
Interview problems
Find Maximum Subarray Sum Using Prefix Sums
Description:
In this post, I’m sharing an alternate solution to the maximum subarray sum problem using prefix sums. This method optimizes the process by maintaining a running sum and calculating the difference between the current sum and the minimum sum encountered so far. Explanation:
This approach ensures that we only traverse the array once, making the time complexity O(n).
#define ll long long int
long long maxSubarraySum(vector<int> arr, int n)
{
vector<pair<ll, ll>> temp(n);
ll minSum = 0, maxSum = INT_MIN, diff = INT_MIN;
for (ll i = 0; i < n; i++) {
temp[i].first = i;
if (i > 0) {
temp[i].second = temp[i - 1].second + arr[i];
} else {
temp[i].second = arr[i];
}
minSum = min(minSum, temp[i].second);
maxSum = max(maxSum, temp[i].second);
diff = max(diff, temp[i].second - minSum);
}
return diff;
}
Interview problems
Maximum Subarray Sum
import java.util.* ;
import java.io.*;
public class Solution {
public static long maxSubarraySum(int[] arr, int n) {
// write your code here
long sum=0;
long Maxi=Long.MIN_VALUE;
for(int i = 0;i<n;i++){
sum += arr[i];
if(sum>Maxi){
Maxi=sum;
}
if(sum<0){
sum=0;
}
if(Maxi<0){
Maxi=0;
}
}
return Maxi;
}
}
Interview problems
My submission is failing one test case, any help?
public static long maxSubarraySum(int[] arr, int n) {
int sum = 0, max = 0;
for(int a : arr) {
sum += a;
max = Math.max(max, sum);
sum = Math.max(0, sum);
}
return Math.max(max,0);
}Interview problems
java || Easy solution
public static long maxSubarraySum(int[] arr, int n) {
long maxi=Integer.MIN_VALUE;
long sum=0;
for(int i=0;i<arr.length;i++){
sum+=arr[i];
if(sum>maxi){
maxi=sum;
}
if(sum<0){ //if sum is -ve then no need to carry it forward
sum=0;
}
if (maxi < 0) maxi = 0; //for empty subarray
}
return maxi;
}
Interview problems
Simple solution using Kadane's algo || handling edge cases(return empty array)
long long maxSubarraySum(std::vector<int> arr, int n) {
long long sum = 0, max = 0;
// if there is only one element in array for that
if(n == 1){
return arr[0];
}
for (int i = 0; i < n; i++) {
// adding next element to sum variable
sum += arr[i];
if (sum > max) {
/* after adding new element of array if sum is greater than max element then we have to update max with sum */
max = sum;
}
/* since we need maximum sum so we are avoiding elements which cause sum less than 0*/
if (sum < 0) {
sum = 0;
}
}
// returning maximum sum
return max;
}
