[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.
kadane-algorithm

// 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






























































































Comments

Post a Comment

Popular posts from this blog

Typical Programs in C/C++

  Sum of two large numbers Difficulty Level :   Medium   Last Updated :  04 Jun, 2019 Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these two numbers. Examples: Input : str1 = "3333311111111111", str2 = "44422222221111" Output : 3377733333332222 Input : str1 = "7777555511111111", str2 = "3332222221111" Output : 7780887733332222 The idea is based on school mathematics. We traverse both strings from end, one by one add digits and keep track of carry. To simplify the process, we do following: 1) Reverse both strings. 2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10. 3) Finally reverse the result. // C++ program to find sum of two large numbers. #include<bits/stdc++.h> using namespace std;     // Function for finding sum of la...
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structur...
Read more
Image
  C Program to Check if a Given String is Palindrome // A function to check if a string str is palindrome void isPalindrome( char str[]) {      // Start from leftmost and rightmost corners of str      int l = 0;      int h = strlen (str) - 1;          // Keep comparing characters while they are same      while (h > l)      {          if (str[l++] != str[h--])          {              printf ( "%s is Not Palindrome" , str);              return ;          }      }      printf ( "%s is palindrome" , str); }     // Driver program to test above function int main() {...
Read more