[10 Feb 2020] Largest Sum Contiguous Subarray

Largest Sum Contiguous Subarray

Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

// C++ program to print largest contiguous array sum #include<iostream> #include<climits> using namespace std;    int maxSubArraySum(int a[], int size) {     int max_so_far = INT_MIN, max_ending_here = 0;        for (int i = 0; i < size; i++)     {         max_ending_here = max_ending_here + a[i];         if (max_so_far < max_ending_here)             max_so_far = max_ending_here;            if (max_ending_here < 0)             max_ending_here = 0;     }     return max_so_far; }    /*Driver program to test maxSubArraySum*/ int main() {     int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};     int n = sizeof(a)/sizeof(a[0]);     int max_sum = maxSubArraySum(a, n);     cout << "Maximum contiguous sum is " << max_sum;     return 0; }

Output:

Maximum contiguous sum is 7

import java.io.*; // Java program to print largest contiguous array sum import java.util.*;    class Kadane {     public static void main (String[] args)     {         int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};         System.out.println("Maximum contiguous sum is " +                                        maxSubArraySum(a));     }        static int maxSubArraySum(int a[])     {         int size = a.length;         int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;            for (int i = 0; i < size; i++)         {             max_ending_here = max_ending_here + a[i];             if (max_so_far < max_ending_here)                 max_so_far = max_ending_here;             if (max_ending_here < 0)                 max_ending_here = 0;         }         return max_so_far;     } }

Output:

Maximum contiguous sum is 7

# Python program to find maximum contiguous subarray     # Function to find the maximum contiguous subarray from sys import maxint def maxSubArraySum(a,size):             max_so_far = -maxint - 1     max_ending_here = 0             for i in range(0, size):         max_ending_here = max_ending_here + a[i]         if (max_so_far < max_ending_here):             max_so_far = max_ending_here            if max_ending_here < 0:             max_ending_here = 0        return max_so_far     # Driver function to check the above function  a = [-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7] print "Maximum contiguous sum is", maxSubArraySum(a,len(a))     #This code is contributed by _Devesh Agrawal_

Output:

Maximum contiguous sum is 7