Introduction to Microservice Architecture Using SpringBoot - Part 1

 

Q-4) Kadane's Algorithm 

Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.

Example 1:

Input:
N = 5
Arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which 
is a contiguous subarray.

Example 2:

Input:
N = 4
Arr[] = {-1,-2,-3,-4}
Output:
-1
Explanation:
Max subarray sum is -1 
of element (-1)

Solution : 

 import java.io.*;  
 class Main {  
      public static void main (String[] args) throws IOException {  
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
           int t = Integer.parseInt(br.readLine().trim()); //Inputting the testcases  
           while(t-->0){  
             //size of array  
             int n = Integer.parseInt(br.readLine().trim());  
             int arr[] = new int[n];  
             String inputLine[] = br.readLine().trim().split(" ");  
             //adding elements  
             for(int i=0; i<n; i++){  
               arr[i] = Integer.parseInt(inputLine[i]);  
             }  
             Solution obj = new Solution();  
             //calling maxSubarraySum() function  
             System.out.println(obj.maxSubarraySum(arr, n));  
           }  
      }  
 }   
 class Solution{    
   long maxSubarraySum(int arr[], int n){  
    int max=arr[0],sum=0;  
   for(int i=0;i<n;i++)  
   {  
     sum+=arr[i];  
     max=Math.max(sum,max);  
     if(sum<0)  
     sum=0;  
   }  
     return max;  
   }  
 }  

Question Link:  https://practice.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1#

Company Tags

 24*7 Innovation Labs Accolite Amazon Citrix D-E-Shaw FactSet Flipkart Hike Housing.com MetLife Microsoft Morgan Stanley Ola Cabs Oracle Payu Samsung Snapdeal Teradata Visa Walmart Zoho Google Adobe Arcesium