---
# System prepended metadata

title: Max Slice in array

---

# Max Slice in array

- There is a given *non-empty* array A of N integers.
- We call a "slice" of array A, a pair of integers (i, j) such that 0 <= i <= j < N.
- The sum of the slice is the total of all values of array A between index i and j including both marginal values.

[-3,100,-10] => 100
[-3,100, -10, 20] => 110
[-3,1000,-10, 0, -500, 20, -1000, 1000, 1000, -1000] => 2000
[-6,-3,-10,-500,-1000, -100, -100] (max slice is 0)

Assumptions:
* Each element of array A is a positive or negative integer within the range [- 100 000, 100 000] 
* N is an integer smaller than 1 000 000.
* When the max slice sum is negative function should return 0.

```python=3.8
def max_sum(array):
    running_sum = 0
    maximal_sum = 0
    for element in array:
        if element + running_sum > 0:
            running_sum += element 
        else:
            running_sum = 0
        if running_sum > maximal_sum :
            maximal_sum = running_sum
    return maximal_sum 

```





## Interview question: Guest at party

Consider a big party where a log register for guest’s entry and exit times is maintained. Find the time at which there are maximum guests in the party. Note that entries in register are not in any particular order.

Example Input: 
	arrivals = [1, 2, 9, 5, 5]
    exits    = [4, 5, 12, 9, 12]

```python=3.8
def routine(arrivals, exits):
    arrivals = sorted(arrivals)
    exits = sorted(exits)
    count = 0
    max_value = 0
    max_time = 0
    start = min(arrivals[0], exits[0])
    end = max(arrivals[-1], exits[-1])
    cursor_arrivals = 0
    cursor_exits = 0
    for timestamp in range(start, end+1):
        while arrivals[cursor_arrivals] == timestamp:
            count += 1
            cursor_arrivals += 1
            if cursor_arrivals == len(arrivals):
                cursor_arrivals = 0 
                break
        while exits[cursor_exits] == timestamp:
            count -= 1
            cursor_exits += 1
            if cursor_exits == len(exits):
                cursor_exits = 0
                break
        if count > max_value:
            max_value = count
            max_time = timestamp
    return max_time

```
