2022-08-28-Amazon笔试

// 求所有前缀和和后缀和中的最大值
// 没要求一次遍历
long 発(vector<int> a)
{
    unsigned int n = a.size(); // >0
    long maxSum = a[0], minSum = a[0], sum = a[0];
    for (unsigned int i = 1; i < n; i++)
    {
        sum += a[i];
        maxSum = max(maxSum, sum);
        if (i != n - 1)
            minSum = min(minSum, sum);
    }
    return max(maxSum, sum - minSum);
}

// abs() 用不了不知道为啥
// 求数组最左边的某个位置（即相同时取左边的）
// 使得 这位置左边)的和的平均值 与 这位置[右边的和的平均值 的绝对值最小
// 没要求几次遍历
int 髪(vector<int> a)
{
    long sum = accumulate(a.begin(), a.end(), OLL);
    unsigned int n = a.size();
    unsigned long minDiff = max(-sum, sum);
    long pS = 0;
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
        pS += a[i];
        long t = pS / (i + 1) - (sum - pS) / (n - i - 1);
        if (t < 0)
            t = -t;
        if (minDiff > t)
        {
            minDiff = t;
            ans = i + 1;
        }
    }
    return ans;
}