Max sum contiguous subarray

Problem statement:- Program to Find the Max sum contiguous subarray.

Example:-

              Input : Given 

                                size=6

                                 arr[]=[4,6,8,10,12,14]

             Output:  Maximum_sum=40

Data requirement:-

   Input Data:- size, arr

  Output Data:-Maximum_Sum

  Additional Data:- i,j,p

Program in C

Here is the source code of the C Program to Find the largest sum contiguous subarray.

Code:

#include<stdio.h>

main()

{

    printf("Enter the size of the array:");

    int size;

    scanf("%d",&size);

    int arr[size];

    int i,j,p;

    printf("Enter the Element of the array:\n");

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

    {

        scanf("%d",&arr[i]);

    }

    int Maximum_Sum=0;

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

    {

         for(j=i;j<size;j++)

          {

              int sum=0;

         for(p=i;p<j;p++)

          {

              sum+=arr[p];

          }

          if(sum>=Maximum_Sum)

          {

              Maximum_Sum=sum;

          }

          }

    }

     printf("Maximum sum of Contiguous Subarray is %d",Maximum_Sum);

}

Input/Output:

Enter the size of the array:6

Enter the Element of the array:

4 6 8 10 12 14

Maximum sum of Contiguous Subarray is 40

Program in C++

Here is the source code of the C++ Program to Find the Max sum contiguous subarray.

Code:

#include<iostream>

using namespace std;

int main()

{

    cout<<"Enter the size of the array:";

    int size;

    cin>>size;

    int arr[size];

    int i,temp=0,j,p;

    cout<<"Enter the Element of the array:\n";

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

    {

        cin>>arr[i];

    }

    int Maximum_Sum=0;

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

    {

         for(j=i;j<size;j++)

          {

              int sum=0;

         for(p=i;p<j;p++)

          {

              sum+=arr[p];

          }

          if(sum>=Maximum_Sum)

          {

              Maximum_Sum=sum;

          }

          }

    }

     cout<<"Maximum sum of Contiguous Subarray is "<<Maximum_Sum;

}

Input/Output:

Enter the size of the array:5

Enter the Element of the array:

8 9 7 6 4

Maximum sum of Contiguous Subarray is 30

Program in Java

Here is the source code of the Java Program to Find the largest sum contiguous subarray.

Code:

import java.util.Scanner;

public class MaxSumSubarray {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

  System.out.println("Enter the size of the array:");

     int size,i,j,p;

     size=sc.nextInt();

     int arr[ ]=new int[size];

  System.out.println("Enter the Element of the array:");

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

     {

         arr[i]=sc.nextInt();

     }

      int Maximum_Sum=0;

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

     {

          for(j=i;j<size;j++)

           {

               int sum=0;

          for(p=i;p<j;p++)

           {

               sum+=arr[p];

           }

           if(sum>=Maximum_Sum)

           {

               Maximum_Sum=sum;

           }

           }

     }

     System.out.println("Maximum sum of Contiguous Subarray is "+Maximum_Sum);

              sc.close();

}

}

Input/Output:

Enter the size of the array:

4

Enter the Element of the array:

10 5 6 12

Maximum sum of Contiguous Subarray is 21

Program in Python

Here is the source code of the Python Program to Find the Max sum contiguous subarray.

Code:

arr=[]

size = int(input("Enter the size of the array: "))

print("Enter the Element of the array:")

for i in range(0,size):

    num = int(input())

    arr.append(num)

Maximum_Sum=0

for i in range(0,size):

    for j in range(i, size):

        sum=0

        for p in range(i, j):

            sum+=arr[p]

        if sum>=Maximum_Sum:

             Maximum_Sum=sum

print("Maximum sum of Contiguous Subarray is ",Maximum_Sum)

Input/Output:

Enter the size of the array: 4

Enter the Element of the array:

13

3

14

4

Maximum sum of Contiguous Subarray is  30

More:-

C/C++/Java/Python Practice Question