Question

In class we discussed an approach that yields a Θ(n) algorithm for solving the maximum subarray problem. This approach incrementally calculates the maximum subarray for A[1..j] that uses A[j], and then uses that value to calculate the maximum subarray for A[1..j+1] that uses A[j+1]. The answer is the maximum of all those n calculated values. Write pseudocode for a version of this algorithm that instead works from the right side of the array to the left. That is, it calculates the maximum subarray for A[j..n] that uses A[j], and then use that result to calculate the maximum subarray for A[j-1..n] that uses A[j-1]

Answer 1

Pseudocode for the above problem is as follows-

Initialize: max_so_far = 0 max_ending_here = 0 Loop for each element of the array from right to left (a) max_ending_here = max_ending_here + a[i] (b) if(max_ending_here < 0) max_ending_here = 0 (c) if(max_so_far < max_ending_here) max_so_far = max_ending_here return max_so_far C++ Code- 

 #include<iostream> #include<climits> using namespace std; //function to calculate max. subarray sum int maxSubArraySum(int a[], int size) { int max_so_far = INT_MIN, max_ending_here = 0; //traversing the array right to left for (int i = size-1; i >= 0; i--) { //finding the maximum subarray sum 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 find maxSubArraySum*/ int main() { //taking input int n; cin>>n; int a[n+1]; for(int i=0;i<n;i++) cin>>a[i]; //calling the function int max_sum = maxSubArraySum(a, n); cout << "Maximum contiguous sum is " << max_sum; return 0; } 

Input and Output-


If the answer helped then please upvote, it means a lot.
And for any queries feel free to comment.