Maximum Subarray

Maximum Subarray Problem

Problem Description:

Given a sequence of n real numbers A(1) … A(n), determine a contiguous subsequence A(i) … A(j) for which the sum of elements in the subsequence is maximized.


Problem Solution:

We will proceed in a linear fashion maintaining overall_max and current_max variables. If adding the current element to current_max results in overall maximum value, we will replace the value of overall_max variable. Otherwise, we will proceed furthere.


Expected Input and Output:

Case-1:

A[]={2,4,6,8}

maximum contiguous subarry= {2, 4, 6, 8}

maximum contiguous subarray sum= 20


Case-2:

A[]={-2, 3, -7, 5, -9}

maximum contiguous subarry= {5}

maximum contiguous subarray sum= 5


Case-3:

A[]={3, -4, 7, -9, 8, 7}

maximum contiguous subarry= {8, 7}

maximum contiguous subarray sum= 15

 

A[]={3, -4, 9, -8, 8, 7}

maximum contiguous subarry= {9, -8, 8, 7}

maximum contiguous subarray sum= 16


Case-4:

A[]={3, -4, 9, -8, 8, 7}

maximum contiguous subarry= {9, -8, 8, 7}

maximum contiguous subarray sum= 16


Program/Source Code for Brute force solution:

Here is source code of the C++ Program to Solve Kadane’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.


#include<iostream>

using namespace std;

//This function will check every contiguous subarray and return the sum of maximum subarray

int maxSubarraySum(int a[], int n)

{

    int overall_sum=0;  //overall maximum subarray sum

    int new_sum;

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

    {

        //find the maximum subarray sum of the subarray starting from a[i]

        new_sum=0;

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

        {

            new_sum+=a[j];

            if(new_sum>overall_sum)

            {

                overall_sum=new_sum;

            }

        }

    }

    return overall_sum;

}

int main()

{

    int i,n;

    cout<<"Enter the number of elements in the array  ";

    cin>>n;

    int a[n];

    //read the vector

    cout<<"enter the elements in the array"<<endl;

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

    {

        cin>>a[i];

    }

    //now,make a call to kadane function to calculate maximum subarray sum

    cout<<endl<<"The maximum subarray sum for the given array is "<<maxSubarraySum(a,n); 

    return 0;

}


Program/Source Code for Dynamic Programming solution:

Here is source code of the C++ Program to Solve Kadane’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.


#include<iostream>

using namespace std;

int kadane(int a[], int n)

{

    int overall_sum=0;  //overall maximum subarray sum

    int new_sum=0;      //sum obtained by including the current element

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

    {

        //new_sum is the maximum value out of current element or the sum of current element

        //and the previous sum

        new_sum=max(a[i], new_sum+a[i]);

        //if the calculated value of new_sum is greater than the overall sum,

        //it replaces the overall sum value

        overall_sum=max(overall_sum, new_sum);

    }

    return overall_sum;

}

 

int main()

{

    int i,n;

    cout<<"Enter the number of elements in the array  ";

    cin>>n;

    int a[n];

    //read the vector

    cout<<"enter the elements in the array"<<endl;

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

    {

        cin>>a[i];

    }

    //now,make a call to kadane function to calculate maximum subarray sum

    cout<<endl<<"The maximum subarray sum for the given array is "<<kadane(a,n); 

    return 0;

}

Program Explanation:

In the main function, we ask the user to input the elements of the array. We pass this array to the function kadane as parameter. This function will calculate the expected result and return it. The returned value will be displayed.


Runtime Test Cases:

Case-1:

Enter the number of elements in the array 4

enter the elements in the array

2      

4

6

8

The maximum subarray sum for the given array is 20.



Let's see how implement the solution for this problem by using List predefined data type in java 😀:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.


Example 2:

Input: nums = [1]

Output: 1


Example 3:

Input: nums = [0]

Output: 0


Example 4:

Input: nums = [-1]

Output: -1


Example 5:

Input: nums = [-2147483647]

Output: -2147483647

 


Constraints:

1 <= nums.length <= 2 * 104

-231 <= nums[i] <= 231 - 1


Program:

class Solution {

    public int maxSubArray(int[] nums) {

        // for(int i:nums){

        //     if ( ( (i>=(Math.pow(-2, 31)) ) && (i<= (Math.pow(2, 31) -1))) )

        //     {

        //         continue;

        //     }

        //     else

        //     {

        //         return 0;

        //     }

        // }

        List<Integer> list = new ArrayList<Integer>();

        Integer i, mx=nums[0];

        list.add(nums[0]);

        for(i=1;i<nums.length;i++)

        {

            Integer k =  nums[i]+list.get(i-1);

            list.add(Math.max(nums[i], k));

        }

        System.out.println(list);

        for(Integer j:list)

        {

            System.out.println(j + " " +  mx);

            if(j>mx)

            {

                mx = j;

            }

        }

        return mx;

    }

} 


Execution:

Successfully Executed








Reference👉 Maximum Subarray || Kadane’s Algorithm – Dynamic Programming Solution


                                                                  Happy Coding 💻:-)


Comments

Post a Comment

Popular posts from this blog

Valid Username Regular Expression

Valid Username Regular Expression: Problem Description: You are updating the username policy on your company's internal networking platform. According to the policy, a username is considered valid if all the following constraints are satisfied: The username consists of 8 to 30 characters inclusive. If the username consists of less than  or greater than 8 characters, then it is an invalid username. The username can only contain alphanumeric characters and underscores (_). Alphanumeric characters describe the character set consisting of lowercase characters[a-z] , uppercase characters[A-Z] , and digits[0-9]. The first character of the username must be an alphabetic character, i.e., either lowercase character [a-z] or uppercase character [A-Z]. Update the value of regularExpression field in the UsernameValidator class so that the regular expression only matches with valid usernames. Input Format The first line of input contains an integer , describing the total number of usernames. Ea...
Read more

Rotate String in Right Direction in java

Rotate String in Right Direction in java: Program: import java.util.*; public class RotateString { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); char[] ch = new char[n]; for(int i=0;i<n;i++) { ch[i] = s.next().charAt(0); } int r = s.nextInt(); char temp = 'a'; r=r%n; while(r>0) { temp = ch[n-1]; for(int i = n-1; i>0;i--) { ch[i] = ch[i-1]; } ch[0] = temp; System.out.println("r: " + r); for(int i=0;i<n;i++) { System.out.print(ch[i]); } System.out.println(); r--; } for(int i=0;i<n;i++) { System.out.print(ch[i]); } } } Output : 5 a s d f g 3 r: 3 gasdf r: 2 fgasd r: 1 dfgas dfgas                                                            Happy Coding 💻:-)
Read more

Java MCQ's

1) Predict the output of following Java Programs. Program 1: // filename Main.java  class Test {      protected int x, y;  }  class Main {      public static void main(String args[]) {          Test t = new Test();          System.out.println(t.x + " " + t.y);      }  }  Output:  0 0 Explanation: In Java, a protected member is accessible in all classes of same package and in inherited classes of other packages. Since Test and Main are in same package, no access related problem in the above program. Also, the default constructors initialize integral variables as 0 in Java (See this GFact for more details). That is why we get output as 0 0. Program 2: // filename Test.java  class Test {      public static void main(String[] args) {          for(int i = 0; 1; i++) {              System.ou...
Read more