To solve this problem, we need to find the maximum sum of a contiguous subarray within a given array of integers. This is a classic problem that can be efficiently solved using Kadane's Algorithm, which runs in linear time.

Approach

The key insight of Kadane's Algorithm is to keep track of two values as we iterate through the array:

1. max_current: The maximum sum of a subarray ending at the current position. This value is updated by choosing between starting a new subarray at the current element or extending the previous subarray by adding the current element.
2. max_global: The maximum sum of any contiguous subarray encountered so far. This value is updated whenever max_current exceeds it.

Steps:

1. Read the number of elements n and the array a.
2. Initialize max_current and max_global to the first element of the array (since the subarray must have at least one element).
3. Iterate from the second element to the end of the array:
   • Update max_current as the maximum of the current element or max_current + current element.
   • If max_current is greater than max_global, update max_global.
4. Print max_global as the result.

Solution Code

n = int(input())
a = list(map(int, input().split()))
max_current = max_global = a[0]
for i in range(1, n):
    max_current = max(a[i], max_current + a[i])
    if max_current > max_global:
        max_global = max_current
print(max_global)

Explanation

Let’s take an example array [-2,1,-3,4,-1,2,1,-5,4] to see how the algorithm works:

• Start with max_current = max_global = -2.
• For element 1: max_current = max(1, -2+1=-1) →1; max_global = 1.
• For element -3: max_current = max(-3,1-3=-2) →-2; max_global remains1.
• For element 4: max_current = max(4, -2+4=2) →4; max_global=4.
• For element -1: max_current= max(-1, 4-1=3) →3; max_global remains4.
• For element 2: max_current= max(2,3+2=5) →5; max_global=5.
• For element 1: max_current= max(1,5+1=6) →6; max_global=6.
• For element -5: max_current= max(-5,6-5=1) →1; max_global remains6.
• For element 4: max_current= max(4,1+4=5) →5; max_global remains6.

The final result is 6 (subarray [4,-1,2,1]), which is correct.

Complexity:

• Time: O(n) (linear pass through the array).
• Space: O(1) (constant extra space, excluding input storage).

This approach efficiently computes the desired result with optimal time and space complexity. The code provided in the problem statement is already correct and implements this solution.

作者声明:本文包含人工智能生成内容。