logo
  • Home
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

Next Page »

C++ Program to Find the maximum subarray sub using Divide and Conquer Approach

Posted on July 29, 2013 by Manish

This is a C++ program to find the maximum subarray sum using divide and conquer approach.

Problem Description

1. This algorithm implements the divide and conquer approach to find the sub-array having a maximum sum.
2. The worst case time complexity of the algorithm is O(n*log(n)).

Problem Solution

1. Take the input of the integer array.
2. Using divide and conquer approach break the array.
3. Compute the individual sum and combine them, to get the global maximum sum.
4. Exit.

Program/Source Code

C++ Program to find the maximum subarray sum using divide and conquer approach.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include<iostream>
 
using namespace std;
 
// A function to find the maximum of two integers.
int max(int a, int b)
{
	return (a > b)? a:b;
}
 
// A function to find the maximum sum sub-array which includes mid of the sub-array.
int MaxCrossingSum(int arr[], int low, int mid, int high)
{
	// Include elements having index value less than or equal to the mid.
	int sum = 0;
	int leftpartsum = -1;
	for (int i = mid; i >= low; i--)
	{
		sum = sum + arr[i];
		if (sum > leftpartsum)
			leftpartsum = sum;
	}
 
	// Include elements having index value greater mid.
	sum = 0;
	int rightpartsum = -1;
	for (int i = mid+1; i <= high; i++)
	{
		sum = sum + arr[i];
		if (sum > rightpartsum)
			rightpartsum = sum;
    }
 
	// Return sum of elements on left and right of mid.
	return leftpartsum + rightpartsum;
}
 
// Returns sum of maxium subarray sum.
int MaxSubArraySum(int arr[], int low, int high)
{
	int mid;
	// If low index is equal to the high index h then the subarray contains only one element.
	if (low == high)
		return arr[low];
 
	// Otherwise find the mid index and proceed.
	mid = (low + high)/2;
 
	// Maximum sum sub-array can be either in the left part, right part or covering elements from both parts.
	return max(max(MaxSubArraySum(arr, low, mid), MaxSubArraySum(arr, mid+1, high)), MaxCrossingSum(arr, low, mid, high));
}
 
int main()
{
	int n, i;
	cout<<"Enter the number of data element in the array: ";
	cin>>n;
 
    int a[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>a[i];
	}
 
	// Print the maximum sub-array sum.
	cout<<"\nMaximum sub-array sum is: "<<MaxSubArraySum(a, 0, n-1);
 
	return 0;
}
Program Explanation

1. Take the input of the number of elements in the array and the data array.
2. Call MaxSubArraySum(), with data array, start and end index in the argument list.
3. Inside MaxSubArraySum(), recursively break the array into two equal parts.
4. Compare the sub-array sum from the left part, right part and the combined sum of the array.
5. For combined sum, call MaxCrossingSum(), it computes the right and left part sum and return their addition.
6. Return to main and print the maximum sub-array sum.
7. Exit.

Runtime Test Cases
Case 1:
Enter the number of data element in the array: 10
Enter element 1: 1
Enter element 2: 2
Enter element 3: 5
Enter element 4: -9
Enter element 5: 6
Enter element 6: 9
Enter element 7: -10
Enter element 8: 2
Enter element 9: 3
Enter element 10: 1
 
Maximum sub-array sum is: 15
Case 2:
Enter the number of edges for the random graphs: 50
 
The generated random graph is:
        1-> { 15   3   17    }
        2-> { 8   8   12   17   12   4   7   10    }
        3-> { 5   16   14   13   14   18   11   1   19    }
        4-> { 12   2   10   7    }
        5-> { 10   3   12   14   8   9   15   20    }
        6-> { 6   7    }
        7-> { 8   9   6   2   17   4    }
        8-> { 2   2   17   7   20   5    }
        9-> { 14   7   5   14   12    }
        10-> { 5   13   19   11   4   2    }
        11-> { 3   10   11    }
        12-> { 2   5   19   4   2   9    }
        13-> { 3   10    }
        14-> { 3   3   5   9   9    }
        15-> { 1   16   5    }
        16-> { 3   19   15   17    }
        17-> { 8   2   16   1   7    }
        18-> { 3   20   19    }
        19-> { 19   16   12   10   18   3    }
        20-> { 8   18   5    }

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

» Next Page - C++ Program to Find the maximum subarray sum O(n^2) time(naive method)
« C++ Program for Topological Sorting in Graphs
C++ Program to Find the maximum subarray sum O(n^2) time(naive method) »

Deep Dive @ Sanfoundry:

  1. C# Programming Examples on LINQ
  2. C Programming Examples using Recursion
  3. C# Programming Examples on Exceptions
  4. C Programming Examples on Searching and Sorting
  5. C Programming Examples on Combinatorial Problems & Algorithms
  6. C# Programming Examples on Arrays
  7. C Programming Examples on Arrays
  8. C# Programming Examples on Sorting
  9. C++ Programming Examples on Combinatorial Problems & Algorithms
  10. Java Programming Examples on Combinatorial Problems & Algorithms
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below:
LinkedIn | Facebook | Twitter | Google+

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
TOS & Privacy
Jobs
Bangalore Training
Online Training
SAN Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry