Maximum Happiness

You are given a sequence of n integers representing the happiness values of flowers. Your task is to compute the maximum total happiness of any continuous (contiguous) segment (subarray) of these values.

This is a classic problem that can be solved using Kadane's algorithm. The algorithm is based on the following recurrence: $$ dp[i] = \max(a[i],\; dp[i-1] + a[i]) $$ where a[i] is the happiness value at the i-th position. The answer is the maximum value among all dp[i] values.

Try to achieve a solution with a time complexity of \(O(n)\).

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains an integer \(n\) denoting the number of flowers.
• The second line contains \(n\) space-separated integers representing the happiness values.

outputFormat

Output a single integer to stdout representing the maximum possible total happiness of any continuous segment of the array.

9
-2 1 -3 4 -1 2 1 -5 4

6