Maximum Luxury Sum

You are given an integer \(N\) representing the number of rooms and a sequence of \(N\) integers \(lux_1, lux_2, \dots, lux_N\) where each \(lux_i\) represents the luxury level of the \(i\)-th room. Your task is to select a contiguous subarray (possibly empty) such that the sum of the selected luxury levels is maximized. Note that if all luxury levels are non-positive, you should return 0.

In mathematical terms, you need to compute the value:

[ S = \max_{1 \leq i \leq j \leq N} \left( \sum_{k=i}^{j} lux_k \right), ]

with the convention that if no positive sum can be obtained, \(S = 0\).

inputFormat

The first line contains a single integer \(N\) (the number of rooms). The second line contains \(N\) space-separated integers representing the luxury levels of each room.

outputFormat

Output a single integer which is the maximum sum of luxury levels of a contiguous subarray. If all numbers are non-positive, output 0.

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

6