Question

Given a vector of N elements, find the maximum sum subarray by squaring at most one element.

Test case 1 : -1 -2 3 -2 3

Output : The given elements are {-1 -2 3 -2 3}. The subarray{3,-2,3} with squaring 3 will give the maximum sum as 10.

Test case 2: -4 -4 -2 5 2 -1

Output : The given elements are {-4 -4 -2 5 2 -1}. The subarray {5 2} with squaring 5 will give maximum sum as 27.

My own intuition

Use Kadane’s algorithm as base.

int n = nums.length;
        int maxNormal = Integer.MIN_VALUE;  // Maximum sum found so far
        int maxEndingHere = 0;  // Current max subarray sum ending at the current index
        for (int i = 0; i < n; i++) {
            maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]); // Update the current max sum
            maxNormal = Math.max(maxNormal, maxEndingHere); // Update the global max if the current is greater
        }
        return maxNormal; // Return the maximum sum found

What changes/tweaks do I need to do in the above for mapping it to the current question? I went through the articles on the internet (geeksforgeeks and algomonster, but the explanation didn’t work for me)