Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Maximum Subarray Sum

Moderate
0/80
Average time to solve is 25m
56 upvotes
Asked in companies
Paytm (One97 Communications Limited)AmazonSnapdeal

Problem statement

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.


For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.


Given the array [-5, -1, -8, -9], the maximum sum would be -1.


Follow up: Do this in O(N) time.

Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first line of input contains size of array, which is denoted by N and second line of input contains N space separated integers.
Output format:
The first and only line of output should print the maximum subarray sum, as described in the description.
Constraints:
1 <= N <= 10^6
1 <= K <= N
Time limit: 1 sec 
Sample Input 1:
4 1
1 2 3 4
Sample Output 1:
4
Sample Input 2:
6 2
2 7 3 6 7 7 
Sample Output 2:
14

Explanation for Sample Output 2:

There are 5 subarrays of size 2 in this array. They are {2, 7}, {7, 3}, {3, 6}, {6, 7}, {7, 7}. Since the subarray {7, 7} has the maximum sum among all the subarrays, the output will be 7 + 7 = 14
Hint

Is there a way to just check all k-subarrays one by one and find the maximum element for each?

Approaches (3)
Brute Force Approach
  1. Create a nested loop. The outer loop will go from i = 0 to i = n - k. This will cover the starting indices of all k-subarrays
  2. The inner loop will go from j = i to j = i + k - 1. This will cover all the elements of the k-subarray starting from index i
  3. Keep track of the maximum element in the inner loop and print it.
Time Complexity

O(N * K) where N is the length of the input array and K is the size of the subarray.

Space Complexity

O(1) because the extra space being used (looping variables, maximum element) is constant for any N and K

Code Solution
(100% EXP penalty)
Maximum Subarray Sum
All tags
Sort by
Search icon

Interview problems

Java Code

import java.util.Scanner;


 

public class Main {


 

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);


 

        if (scanner.hasNextInt()) {

            int N = scanner.nextInt();

        


 

            int[] arr = new int[N];


 

            for (int i = 0; i < N && scanner.hasNextInt(); i++) {

                arr[i] = scanner.nextInt();

            }


 

            System.out.println(maxSubarraySum(arr, N));

        } else {

            System.out.println("No input provided.");

        }


 

        scanner.close();

    }


 

    public static int maxSubarraySum(int[] arr, int n) {

        if (n == 0) return 0;


 

        int maxSum = Integer.MIN_VALUE;

        int sum = 0;


 

        for (int i = 0; i < n; i++) {

            if(sum<0){

                sum=0;

            }

            sum=sum+arr[i];

            if(sum>maxSum){

                maxSum=sum;

            }

        }


 

        return maxSum;

    }

}


 

programming

java

51 views
0 replies
0 upvotes

Interview problems

Java Better than 99%- Maximum Subarray Sum

import java.util.Scanner;

 

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

 

 

if (scanner.hasNextInt()) {

int N = scanner.nextInt();

int K = scanner.nextInt();

 

int[] arr = new int[N];

 

for (int i = 0; i < N && scanner.hasNextInt(); i++) {

arr[i] = scanner.nextInt();

}

 

System.out.println(maxSubarraySum(arr, N));

} else {

System.out.println("No input provided.");

}

 

scanner.close();

}

 

public static int maxSubarraySum(int[] arr, int n) {

if (n == 0) return 0;

 

// Initialize variables

int currentMax = arr[0];

int globalMax = arr[0];

 

 

for (int i = 1; i < n; i++) {

 

currentMax = Math.max(arr[i], currentMax + arr[i]);

 

 

globalMax = Math.max(globalMax, currentMax);

}

 

return globalMax;

}

}

 

94 views
0 replies
0 upvotes

Interview problems

C++ easy solution Kadane’s Algorithm

#include <bits/stdc++.h>
using namespace std;

int findMaxSum(vector<int>& arr, int n) {
    int maxSum = arr[0];
    int currentSum = arr[0];

    for (int i = 1; i < n; i++) {
        currentSum = max(arr[i], currentSum + arr[i]);
        maxSum = max(maxSum, currentSum);
    }

    return maxSum;
}

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << findMaxSum(arr, n) << endl;

    return 0;
}
334 views
0 replies
0 upvotes

Interview problems

Java Code

import java.util.Scanner;

 

public class Main {

 

    

    public static void main(String[] args) {

        /* Your class should be named Main.

            * Read input as specified in the question.

            * Print output as specified in the question.

        */

 

        // Write your code here

        Scanner sc = new Scanner(System.in);

        int sixe = sc.nextInt();

 

        int arr[] =new int[sixe];

 

        for(int i=0; i<sixe; i++){

            arr[i] = sc.nextInt();

        }

 

        int maxi = arr[0], sum =0;

        int n = arr.length;

 

        for(int i =0; i< n; i++){

            sum += arr[i];

            maxi = Math.max(sum, maxi);

            if(sum < 0) sum =0;

        }

        System.out.print(maxi);

    }

 

}

80 views
0 replies
0 upvotes

Interview problems

C++ solution::

#include<bits/stdc++.h>

using namespace std;

int main() 

{

    int n;

    cin>>n;

    int arr[n];

   for(int i=0;i<n;i++)

   {

       cin>>arr[i];

   }

        int sum=0,maxsum=arr[0];;

        for(int i=0;i<n;i++)

        {

            sum+=arr[i];

            maxsum=max(maxsum,sum);

            

            if(sum<0)

            {

                sum=0;

            }

        }

           cout<< maxsum;

}

 

257 views
0 replies
0 upvotes

Interview problems

92.59% BETTER , CPP , KADANE ALGO

#include<bits/stdc++.h>

using namespace std;

int main() {

 

    // Write your code here

    int n;

    cin>>n;

    vector<int>v(n);

    for(int i=0;i<n;i++){

        cin>>v[i];

    }

 

    int startindex = 0;

    int endindex = n;

    int maxi = v[0];

    int sum =0 ;

 

        for(int i=0;i<v.size();i++){

            sum = sum+v[i];

            maxi = max(maxi,sum);

            if(sum<0){

                sum= 0;

            }

        }

    

    cout<<maxi<<endl;

    

}

101 views
0 replies
0 upvotes

Interview problems

Easy c++ solution using Kadane's algorithm. BETTER THAN 100%

#include<bits/stdc++.h>

using namespace std;

int main() {

 

    // Write your code here

    int n,maxi,sum=0;

    cin>>n;

    vector <int> v(n);

    for(int i=0;i<n;i++)

        cin>>v[i];

    maxi=v[0];

    for(int i=0;i<n;i++)

    {

        sum=sum+v[i];

        maxi=(sum>maxi)?sum:maxi;

        if(sum<0)

            sum=0;

    }

    cout<<maxi<<endl;

}

141 views
0 replies
0 upvotes

Interview problems

Kadane 's algo

#include<bits/stdc++.h>

using namespace std;

 

int f(vector<int>&v,int n)

{

    int sum=0,maxi=v[0];

    for(int i=0;i<n;i++)

    {

        sum=sum+v[i];

        maxi=max(maxi,sum);

        if(sum<0)

        {

            sum=0;

        }

    }

    return maxi;

 

}

int main() {

     int n;

 

    cin>>n;

 

    vector<int>v(n);

 

    for(int i=0;i<n;i++){

 

        cin>>v[i];

 

    }

 

    cout<<f(v,n)<<endl;

    

}

176 views
0 replies
0 upvotes

Interview problems

better than 100%

#include<bits/stdc++.h>

using namespace std;

 

int f(vector<int>&v,int n){

   int r=0,sum=0;

   int maxi = INT_MIN;

   while(r<n){

       sum+=v[r];

           maxi =max(maxi,sum);

            if(sum<0)sum=0;

       r++;

   }

   return maxi;

}

int main() {

 

    // Write your code here

    int n;

    cin>>n;

    vector<int>v(n);

    for(int i=0;i<n;i++){

        cin>>v[i];

    }

    cout<<f(v,n)<<endl;

}

85 views
0 replies
0 upvotes

Interview problems

C++ Solution || All test case passed || Time Complexity: O(n)

Kadane's Algo

#include<bits/stdc++.h>
using namespace std;

//function to solve the question
int maximumSumSubarray (int* arr, int n) {

	long long maxSum = 0;
	long long currSum = 0;

	for (int i = 0; i < n; i++) {
		currSum += arr[i];

		if (currSum > maxSum) {
			maxSum = currSum;
		}

		if (currSum < 0) currSum = 0;
	}

	return maxSum;
}

int main() {

	int n;
	cin >> n;

	int* arr = new int[n];

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int ans = maximumSumSubarray(arr, n);
	cout << ans << endl;

	delete[] arr;
	arr = NULL;

	return 0;
}
167 views
0 replies
1 upvote
Full screen
Console