lab2.cpp

#include <bits/stdc++.h>
using namespace std;
int maxSumSubarrayRemovingOneEle(int arr[], int n) {
	int fw[n], bw[n];
	int curr = arr[0], maxi = arr[0];
	fw[0] = arr[0];
	for (int i = 1; i < n; i++) {
		curr = max(arr[i], curr + arr[i]);
		maxi = max(maxi, curr);
		fw[i] = curr;
	}
	curr = maxi = bw[n - 1] = arr[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		curr = max(arr[i], curr + arr[i]);
		maxi = max(maxi, curr);
		bw[i] = curr;
	}
	int ans = maxi;
	for (int i = 1; i < n - 1; i++)
		ans = max(ans, max(0, fw[i-1])+max(0, bw[i+1]));

	if (ans == 0) {
		return *max_element(arr, arr + n);
	}
	return ans;
}

int main() {
	cout<<"No. of points: ";
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
	cout << maxSumSubarrayRemovingOneEle(arr, n);
	return 0;
}

/*
Input:

n: The number of elements in the array arr[].
arr[]: The array of integers.
Arrays fw[] and bw[]:

fw[]: Stores the maximum sum subarray that ends at each index i (from left to right).
bw[]: Stores the maximum sum subarray that starts at each index i (from right to left).
Detailed Explanation:
Forward Subarray Calculation (fw[]):

The code first calculates the maximum sum subarray ending at each index i and stores it in fw[].
The current maximum subarray sum up to index i is either the element arr[i] itself or the sum of the current element and the maximum subarray sum ending at the previous index (fw[i-1]).
For each iteration, the algorithm updates the current maximum subarray sum curr, and also keeps track of the overall maximum subarray sum maxi.
Backward Subarray Calculation (bw[]):

Similarly, the code calculates the maximum sum subarray starting from each index i and stores it in bw[]. This is done in reverse order, starting from the end of the array.
The logic is the same as for fw[], but traversing from right to left.
Combining the Results:

After calculating both fw[] and bw[], the algorithm considers removing each element arr[i] (except the first and last element).
For each index i, it checks the sum of two subarrays: one ending at i-1 (fw[i-1]) and one starting at i+1 (bw[i+1]). These two subarrays together simulate removing the element arr[i] and combining the subarrays around it.
The result ans is updated with the maximum value between the current ans and the combined subarrays after removing one element.
Edge Case:

If the answer ans turns out to be 0, it means removing an element doesn't improve the sum, so the maximum element from the array is returned instead.
*/