How can you find the maximum sum subarray in a non-circular array?

To find the maximum sum subarray in a non-circular array, you can use the Kadane's algorithm.

The Kadane's algorithm is an efficient approach that iterates through the array and keeps track of the maximum sum subarray seen so far. It works by maintaining two variables: "maxSoFar" and "maxEndingHere".

Initially, set both variables to the first element of the array. Then, iterate through the array starting from the second element. For each element, update "maxEndingHere" by taking the maximum value between the current element and the sum of the current element and "maxEndingHere".

Next, update "maxSoFar" by taking the maximum value between "maxSoFar" and "maxEndingHere". This step ensures that "maxSoFar" always stores the maximum sum subarray seen so far.

Repeat this process for all elements in the array. Finally, the value of "maxSoFar" will represent the maximum sum subarray in the non-circular array.

Here is an example implementation in Python:

def findMaxSubarray(arr):
maxSoFar = arr[0]
maxEndingHere = arr[0]

for i in range(1, len(arr)):
maxEndingHere = max(arr[i], maxEndingHere + arr[i])
maxSoFar = max(maxSoFar, maxEndingHere)

return maxSoFar

# Example usage
arr = [1, -2, 3, 4, -1, 2, 1, -5, 4]
maxSum = findMaxSubarray(arr)
print("Maximum sum subarray:", maxSum)

In this example, the maximum sum subarray in the given non-circular array [1, -2, 3, 4, -1, 2, 1, -5, 4] is [3, 4, -1, 2, 1], with a sum of 9.