"""
输入一个数组 ht，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。
容器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。
请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量。

容器由任意两个隔板围成，因此本题的状态为两个隔板的索引，记为 [i,j]。

根据题意，容量等于高度乘以宽度，其中高度由短板决定，宽度是两隔板的数组索引之差。设容量为 cap[i,j]，则可得计算公式：
    cap[i,j] = min(ht[i],ht[j]) * (j - i)

贪心策略确定:

- 现选取一个状态 [i, j]，其满足索引 i<j 且高度 ht[i]<ht[j]。
- 若此时将长板 j 向短板 i 靠近，则容量一定变小。因为i仍然是短板。
- 向内移动i，i的高度增大后，容量才可能变大。
- 由此便可推出本题的贪心策略：初始化两指针分列容器两端，每轮向内收缩短板对应的指针，直至两指针相遇。
"""
import math


def max_capacity(ht: list[int]) -> int:
    i, j = 0, len(ht) - 1
    res = 0
    while i < j:
        cap = min(ht[i], ht[j]) * (j - i)
        res = max(res, cap)
        if ht[i] < ht[j]:
            i += 1
        else:
            j -= 1
    return res


"""
最大切分乘积问题：

给定一个正整数 n，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少?

假设我们将 n 切分为 m 个整数因子，其中第 i 个因子记为 ni

贪心策略确定：

根据经验，两个整数的乘积往往比它们的加和更大。假设从 n 中分出一个因子 2，
则它们的乘积为 2(n-2)。我们将该乘积与 n 作比较：
    2*(n-2)>=n  --> n>=4
    
也就是当 n>=4 时，切分出一个 2 后乘积会变大，这说明大于等于 4 的整数都应该被切分。

贪心策略一：如果切分方案中包含 >=4 的因子，那么它就应该被继续切分。最终的切分方案只应出现 1、2、3这三个因子。
    在 1、2、3 这三个因子中，显然 1 是最差的，因为 1*(n-1)<n恒成立。

贪心策略二：在切分方案中，最多只应存在两个 2。因为三个 2，总是可以替换为两个 3，从而获得更大的乘积。

代码实现：
我们无须通过循环来切分整数，而可以利用向下整除运算得到 3 的个数 a，用取模运算得到余数 b，
此时有：
    n = 3a + b
    
请注意，对于 n<=3 的边界情况，必须拆分出一个 1，乘积为 1(n-1)。
"""


def max_product_cutting(n: int) -> int:
    if n <= 3:
        return 1 * (n - 1)

    a, b = n // 3, n % 3
    if b == 1:
        # 当余数为 1 时，将一对 1 * 3 转为 2 * 2
        return int(math.pow(3, a - 1)) * 2 * 2
    if b == 2:
        # 当余数为 2 时不用处理
        return int(math.pow(3, a)) * 2

    # 余数为 0 时不用处理
    return int(math.pow(3, a))