Given an array of integers as input, find the sum of the contiguous su

1.	Given an array of integers as input, find the sum of the contiguous subarray in the array such that its sum is the maximum of all the possible subarrays.
Answer» Example: Input: Arr = {-2, -3, 4, -1, -2, 1, 5, -3} Output: 7 Explanation: The largest contiguous subarray sum is formed by the subarray [4, -1, -2, 1, 5] Approach 1: The very basic approach is to traverse through every possible subarray of the given array and to find the sum of each subarray. We then compare the obtained sum with our answer and update our answer if this sum is greater than the answer. The time complexity in this approach would be O(n^3) and the space complexity would be O(1). We will run a nested loop to consider all the subarrays. Now, INSIDE the nested loop, we will run one more nested loop to find the sum of the elements of the subarray in consideration. We can reduce the time complexity in this case to O(n^2) by maintaining a prefix sum array for the given array. This would help us to eliminate the third nested loop. However, doing so increases the space cost to O(n). We leave the implementation of these approaches for the READERS since they are pretty straightforward. Let us now look at the most optimal solution. Approach 2: In this approach, we follow Kadane's algorithm. The basic idea behind Kadane's approach is to search the array for all positive contiguous segments (max_ending_here is utilized for this). Also, among all positive segments, we maintain track of the maximum total contiguous segment (max_so_far is utilized for this). We compare each positive-sum to max_so_far and update max_so_far if it is more than max_so_far. Solution Code: #include<iostream>using NAMESPACE std;// FUNCTION to find the maximum contiguous subarray sumint findMaxSubArraySum(int arr[], int size){ int max_so_far = arr[0]; int curr_max = arr[0]; for (int i = 1; i < size; i++) { curr_max = max(arr[i], curr_max+arr[i]); max_so_far = max(max_so_far, curr_max); } return max_so_far;} int MAIN(){ int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}; int n = sizeof(arr)/sizeof(arr[0]); int max_sum = findMaxSubArraySum(arr, n); cout << "The maximum contiguous sum for the given array is : " << max_sum; return 0;} Output: 7 Time Complexity: O(n) Space Complexity: O(1) Explanation: In the above code, the function findMaxSubArraySum() takes the input of an array and the size of the array as its parameters and returns the maximum sum for a contiguous subarray of the given array. We keep two variables to find our answer. curr_max holds the current maximum subarray sum whose elements are the array elements just before the current index. max_so_far holds the maximum subarray sum seen so far.

Given an array of integers as input, find the sum of the contiguous subarray in the array such that its sum is the maximum of all the possible subarrays.

Answer»

Example:

Input: Arr = {-2, -3, 4, -1, -2, 1, 5, -3}

Output: 7

Explanation: The largest contiguous subarray sum is formed by the subarray [4, -1, -2, 1, 5]

Approach 1: The very basic approach is to traverse through every possible subarray of the given array and to find the sum of each subarray. We then compare the obtained sum with our answer and update our answer if this sum is greater than the answer. The time complexity in this approach would be O(n^3) and the space complexity would be O(1). We will run a nested loop to consider all the subarrays. Now, INSIDE the nested loop, we will run one more nested loop to find the sum of the elements of the subarray in consideration.

We can reduce the time complexity in this case to O(n^2) by maintaining a prefix sum array for the given array. This would help us to eliminate the third nested loop. However, doing so increases the space cost to O(n).
We leave the implementation of these approaches for the READERS since they are pretty straightforward. Let us now look at the most optimal solution.

Approach 2: In this approach, we follow Kadane's algorithm. The basic idea behind Kadane's approach is to search the array for all positive contiguous segments (max_ending_here is utilized for this). Also, among all positive segments, we maintain track of the maximum total contiguous segment (max_so_far is utilized for this). We compare each positive-sum to max_so_far and update max_so_far if it is more than max_so_far.

Solution Code:

#include<iostream>using NAMESPACE std;// FUNCTION to find the maximum contiguous subarray sumint findMaxSubArraySum(int arr[], int size){ int max_so_far = arr[0]; int curr_max = arr[0]; for (int i = 1; i < size; i++) { curr_max = max(arr[i], curr_max+arr[i]); max_so_far = max(max_so_far, curr_max); } return max_so_far;} int MAIN(){ int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}; int n = sizeof(arr)/sizeof(arr[0]); int max_sum = findMaxSubArraySum(arr, n); cout << "The maximum contiguous sum for the given array is : " << max_sum; return 0;}

Output:

Time Complexity: O(n)

Space Complexity: O(1)

Explanation: In the above code, the function findMaxSubArraySum() takes the input of an array and the size of the array as its parameters and returns the maximum sum for a contiguous subarray of the given array. We keep two variables to find our answer. curr_max holds the current maximum subarray sum whose elements are the array elements just before the current index. max_so_far holds the maximum subarray sum seen so far.

Given an array of integers as input, find the sum of the contiguous subarray in the array such that its sum is the maximum of all the possible subarrays.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment