# Maximum Sum Contiguous Subsequence

#### Problem Statement:

Given an array of positive and negative integers, identify the sub-sequence (set of contiguous elements) with maximum sum**.** 

**Assumptions:** 

1. A sub-sequence contains one (or) more elements.
2. There will always be one positive sub-sequence in the array

**Approach 1: Naive Searching**

At every index position, check for all possible sub-sequences starting with that index position. Finally, output the sub-sequence with maximum value. 

{% code title="Maximum Sum Subarray (Brute Force Approach)" %}

```
int MaxSum1(int A[], int n){
	int result=0;
	int sum;
	for(int i=0;i<n;i++){
		sum=A[i];
		for(int j=i+1;j<n;j++){
			sum=sum+A[j];
			if(result<sum){
				result = sum;
			}
		}
	}
	return result;
}
```

{% endcode %}

Time Complexity Analysis : Number of sub-sequences considered = $$O(n^{2})$$&#x20;

#### Approach 2: Using Divide and Conquer

**Base case :** When the array contains only one element, the maximum sum is the element itself

**Recursive case:** Sub-problems find the maximum sum recorded in a sub-array. To find the solution to the problem, (i.e) To Find the maximum sum sub-sequence for the entire array

1. It may be the sub-sequence with maximum value in the  left sub-array ( $$Sum\_{left}$$)
2. It may be the sub-sequence with maximum value in the  right sub-array ( $$Sum\_{right}$$ )
3. It may be a sub-sequence which starts in the left sub-array and ends in the right sub-array. To find this , use O(n) search adding up elements one after other starting from midpoint to the first element in the left sub-array and record the maximum obtained value . Repeat the same from position mid+1 to the last element in the left sub-array

Maximum sum across the mid-point for the array $$Sum\_{midpoint}$$   = Maximum sum obtained from mid-point to first element in left sub-array + Maximum sum obtained from position mid-point + 1 to the last element in the right sub-array.

Thus, the recursive case finds the maximum sum using the solutions $$Sum\_{left}, Sum\_{right}, Sum\_{midpoint}$$&#x20;

Maximum Sum = $$max(Sum\_{left},Sum\_{right},Sum\_{midpoint})$$&#x20;

{% code title="Divide and Conquer Approach" %}

```
int Maximum(int val1, int val2, int val3){
	return ((val1>val2)&&(val1>val3))?val1:((val2>val1)&&(val2>val3))?val2:val3;
}

int MaxSum2(int A[], int low, int high){

	if(low==high){
		return A[low];
	}
	else{
		int mid = (low+high)/2;
		int val1 = MaxSum2(A,low,mid);
		int val2 = MaxSum2(A,mid+1,high);
		int val3 = midpointSum(A,low,mid,high); // Merge Operation
		int m =Maximum(val1,val2,val3);
		printf("low:%d mid:%d high:%d m:%d\n", low,mid,high,m);
		return m;
	}
}
```

{% endcode %}

{% code title="Merge procedure for D& C" %}

```

int midpointSum(int A[], int low, int mid, int high){
	int MaxLeft = 0, MaxRight=0;
	int lsum=0, rsum=0;
	int i;
	for(i=mid;i>=low;i--){
		lsum = lsum + A[i];
		if(MaxLeft<lsum){MaxLeft=lsum;}
	}
	for(i=mid+1;i<=high;i++){
		rsum = rsum+A[i];
		if(MaxRight<rsum){MaxRight = rsum;}
	}

	return MaxLeft+MaxRight;
}
```

{% endcode %}

Time Complexity analysis : T(n) = 2T(n/2) + O(n). By using master's theorem, T(n)= $$\theta(nlogn)$$&#x20;

**Approach 3: Iterative method**

**Intuition :** negative sub-sequences affect the sum

Maintain sum variable and Iteratively add elements to the sum. Also keep track of the maximum sum recorded. Whenever the sum reaches a negative value, restart the procedure by initializing sum to zero

{% code title="Kadane's algorithm for finding maximum sub array" %}

```
int MaxSum3(int A[], int low, int high){

	int max_so_far = 0;
	int max_ending_here = 0;

	for(int i=low;i<=high;i++){
		max_ending_here = max_ending_here + A[i];
		if(max_ending_here < 0)
			max_ending_here = 0;
		if(max_so_far < max_ending_here)
			max_so_far = max_ending_here;
	}

	return max_so_far;
}
```

{% endcode %}

Time Complexity analysis : Array is scanned only once. Hence records a T(n) = O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://myravithar.gitbook.io/workspace/divide-and-conquer-technique/maximum-sum-contiguous-sub-sequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.