Part-3,Largest Sum Contiguous Subarray

       Largest Sum Contiguous Subarray

 

                                                  Use of Dynamic Programming 
                                                  TIME  COMPLEXITY  O(n)                          

#include<bits/stdc++.h>

using namespace std;



int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];

   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}



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;

}

 

 

                      A Problem & It's Solution 

 

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/      




#include<bits/stdc++.h>

using namespace std;

// Nayeem Shahriar Joy , Applied physics & Electronic Engineering , University of Rajshahi.

int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];

   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}

/* Driver program to test maxSubArraySum */
int main()
{
    int t;
    cin>>t;
    while(t--){
        int x;
        cin>>x;
        int a[x];
        for(int i=0;i<x;i++)
        {
            cin>>a[i];
        }
   int n = sizeof(a)/sizeof(a[0]);
   int max_sum = maxSubArraySum(a, n);
   cout<< max_sum<<endl;
    }
   return 0;
}