Tree Algorithm

Question

Solution

Tree Algorithm

def solution(arr):
    left_id = 0
    right_id = len(arr) - 1

    max_area = 0

    while left_id < right_id:
        if arr[left_id] >= arr[right_id]:
            right_id = right_id - 1
        else:
            left_id = left_id + 1

        area = min(arr[left_id], arr[right_id]) * (right_id - left_id)

        max_area = max(max_area, area)

    return max_area


arr = [2, 1, 8, 6, 2, 5, 4, 8, 3, 7, 1, 2]
print(solution(arr))

Full

Tree Algorithm

from gen.util.print_out_manager import print_out


def solution(arr):
    left_id = 0
    right_id = len(arr) - 1

    max_area = 0

    while left_id < right_id:
        area = min(arr[left_id], arr[right_id]) * (right_id - left_id)
        max_area = max(max_area, area)

        print_out(left_id, right_id, arr[left_id], arr[right_id], area)

        if arr[left_id] >= arr[right_id]:
            right_id = right_id - 1
        else:
            left_id = left_id + 1

    return max_area


arr = [2, 1, 8, 6, 2, 5, 4, 8, 3, 7, 1, 2]
result = solution(arr)

print_out(result)

Step	left_id	right_id	arr[left_id]	arr[right_id]	area
1	0	11	2	2	22
2	0	10	2	1	10
3	0	9	2	7	18
4	1	9	1	7	8
5	2	9	8	7	49
6	2	8	8	3	18
7	2	7	8	8	40
8	2	6	8	4	16
9	2	5	8	5	15
10	2	4	8	2	4
11	2	3	8	6	6

result
49

Simple

Tree Algorithm

from gen.util.print_out_manager import print_out


def solution(arr):
    left_id = 0
    right_id = len(arr) - 1

    max_area = 0

    while left_id < right_id:
        area = min(arr[left_id], arr[right_id]) * (right_id - left_id)
        max_area = max(max_area, area)

        print_out(left_id, right_id, arr[left_id], arr[right_id], area)

        if arr[left_id] >= arr[right_id]:
            right_id = right_id - 1
        else:
            left_id = left_id + 1

    return max_area


arr = [2, 1, 8, 6, 2, 5, 4, 8, 3, 7, 1, 2]
result = solution(arr)

print_out(result)

Step	left_id	right_id	arr[left_id]	arr[right_id]	area
1	0	11	2	2	22
2	0	10	2	1	10
3	0	9	2	7	18
4	1	9	1	7	8
5	2	9	8	7	49
6	2	8	8	3	18
7	2	7	8	8	40
8	2	6	8	4	16
9	2	5	8	5	15
10	2	4	8	2	4
11	2	3	8	6	6

result
49