Scribd
Upload
2 views

Maximum Subarray Sum for LAB

The document discusses the Maximum Subarray Sum problem, which involves finding the sum of the contiguous subarray with the largest sum from a one-dimensional array containing both positive and negative integers. It outlines various approaches to solve the problem, including brute-force methods with time complexities of O(n^3) and O(n^2), as well as a divide and conquer strategy that considers subarrays crossing the midpoint. An example is provided to illustrate the maximum subarray sum for a specific array.

Uploaded by

ssonakshibe22
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views

Maximum Subarray Sum for LAB

The document discusses the Maximum Subarray Sum problem, which involves finding the sum of the contiguous subarray with the largest sum from a one-dimensional array containing both positive and negative integers. It outlines various approaches to solve the problem, including brute-force methods with time complexities of O(n^3) and O(n^2), as well as a divide and conquer strategy that considers subarrays crossing the midpoint. An example is provided to illustrate the maximum subarray sum for a specific array.

Uploaded by

ssonakshibe22
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

Maximum Subarray Sum

Instructor: Dr. Tarunpreet Bhatia


Assistant Professor, CSED
Thapar Institute of Engineering and Technology
Maximum Subarray Sum

• You are given a one dimensional array that may contain


both positive and negative integers, find the sum of
contiguous subarray of numbers which has the largest sum.
• Some properties of this problem are:
• If the array contains all non-negative numbers, the maximum
subarray is the entire array.
• Several different sub-arrays may have the same maximum sum.
• For example, if the given array is {-2, -5, 6, -2, -3, 1, 5, -6},
then the maximum subarray sum is 7
Brute Force
• We can use brute-force to calculate sum of all possible subarray, and then get
the maximum sum.
• Time complexity of brute-force solution will be O(n^3).
• The brute-force solution can be improved to O(n^2) time complexity by
using a variable to store the running sum at all possible positions.
Brute Force Approach I
Brute Force Approach II
Divide and Conquer
• You could divide the array into two equal parts and then recursively find the
maximum subarray sum of the left part and the right part. But what if the
actual subarray with maximum sum is formed of some elements from the
left and some elements from the right?
• The sub-array we’re looking for can be in only one of three places:
• On the left part of the array (between 0 and the mid)
• On the right part of the array (between the mid + 1 and the end)
• Somewhere crossing the midpoint.
Divide and Conquer Approach
Example

You might also like