---
# 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,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.7
def max_slice(arr):
    N = len(arr)
    max_slice = 0
    
    for i in range(N):
        slice_sum = 0
        for j in range(i, N):
            slice_sum += arr[j]
            if slice_sum > max_slice:
                max_slice = slice_sum
    
    return max_slice
```   


[-3,100,-10, 3]
i=0 -> j=2 => -3 + 100 + -10 
i=1 -> j=2 => 100 + -10




# Party Problem

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 time_max_guests(arrivals, exits):
    arrivals.sort()
    exits.sort(reverse=True)
    num_guests = 0
    max_num_guests = 0
    max_time = None
    
    for i, arr_time in enumerate(arrivals):
        while exits[-1] == arr_time:
            exits.pop()
            num_guests -= 1
        
        num_guests += 1
        if num_guests > max_num_guests:
            max_num_guests = num_guests
            max_time = arr_time
        
        if i + 1 < len(arrivals):
            while exits[-1] < arrivals[i+1]:
                exits.pop()
                num_guests -= 1
    
    return max_time

```