子数组最大累加和

53. 最大子数组和

• 返回子数组最大累加和
• 返回子数组的开始和结束位置

int max(int a, int b, int c) {
    int d = a > b ? a : b;
    return d > c ? d : c;
}

// 必须经过mid和mid+1
int maxCrossingSum(int *nums, int left, int mid, int right) {
    int leftMax = nums[mid];
    int rightMax = nums[mid + 1];

    int index = mid;
    int tempMax = 0;
    // 找左边以mid结尾的最大连续子数组的和
    while (index >= left) {
        tempMax += nums[index];
        if (tempMax > leftMax) leftMax = tempMax;
        index--;
    }

    index = mid + 1;
    tempMax = 0;
    // 找右边以mid+1开头的最大连续子数组的和
    while (index <= right) {
        tempMax += nums[index];
        if (tempMax > rightMax) rightMax = tempMax;
        index++;
    }

    return leftMax + rightMax;
}

// 分治
int maxSubArraySum(int *nums, int left, int right) {
    if (left == right) return nums[left];
    // 中偏左
    int mid = left + ((right - left) >> 1);

    // 分三类，包含所有情况
    // 第一类：以mid结尾的
    // 第二类：以mid+1开头的
    // 第三类：经过mid和mid+1的
    return max(maxSubArraySum(nums, left, mid),
               maxSubArraySum(nums, mid + 1, right),
               maxCrossingSum(nums, left, mid, right));
}


int maxSubArray(int *nums, int numsSize) {
    if (numsSize == 0) return 0;
    return maxSubArraySum(nums, 0, numsSize - 1);
}

int max(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int *nums, int numsSize) {
    // dp[i]表示以nums[i]结尾的子数组最大累加和
    int dp[numsSize];
    dp[0] = nums[0];
    for (int i = 1; i < numsSize; ++i)
        dp[i] = max(nums[i], dp[i - 1] + nums[i]);
    int res = 0x80000000;
    for (int i = 0; i < numsSize; ++i)
        if (res < dp[i]) res = dp[i];
    return res;
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 空间压缩
int maxSubArray(int *nums, int numsSize) {
    int pre, cur;
    int res = nums[0];
    pre = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        cur = max(nums[i], pre + nums[i]);
        if (res < cur) res = cur;
        pre = cur;
    }
    return res;
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 记录子数组开头结尾
int maxSubArray(int *nums, int numsSize) {
    int pre = 0x80000000, cur;
    // 最大累加和的子数组的开头结尾
    int left, right;
    int res = nums[0];
    for (right = 0; right < numsSize; ++right) {
        if (pre >= 0) {
            cur = pre + nums[right];
        } else {
            cur = nums[right];
            left = right;
        }
        res = max(cur, res);
        pre = cur;
    }
    printf("left=%d right=%d\n", left, right);
    return res;
}

198. 打家劫舍

• 不能选相邻元素的最大累加和问题

int max(int a, int b) {
    return a > b ? a : b;
}

int rob(int *nums, int numsSize) {
    if (numsSize == 1) return nums[0];
    // dp[i]表示偷i间房子的最大金额
    int dp[numsSize];
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < numsSize; ++i) {
        // 当前位置偷，dp[i] = dp[i-2] + nums[i]
        // 当前位置不偷，dp[i] = dp[i-1]
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }

    return dp[numsSize - 1];
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 空间优化
int rob(int *nums, int numsSize) {
    int left = 0;
    int mid = 0;
    int right = 0;

    for (int i = 0; i < numsSize; ++i) {
        right = max(mid, left + nums[i]);
        left = mid;
        mid = right;
    }

    return right;
}

• 以下写法允许nums包含负数

int max(int a, int b) {
    return a > b ? a : b;
}

int rob(int *nums, int numsSize) {
    if (numsSize == 1)return nums[0];
    if (numsSize == 2)return max(nums[0], nums[1]);
    // dp[i]表示0~i上符合题意的最大累加和
    int dp[numsSize];
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    // 1.不以nums[i]结尾，则返回dp[i-1]，（为啥不是dp[i-1]之前的，因为0~i-1的范围更大）
    // 2.以nums[i]结尾
    //      2.1单独以nums[i]作为子数组，返回nums[i]
    //      2.2包含nums[i]之前的元素，返回dp[i-2]+nums[i]
    // 最终取三者最大值
    for (int i = 2; i < numsSize; ++i)
        dp[i] = max(dp[i - 1], max(nums[i], dp[i - 2] + nums[i]));
    return dp[numsSize-1];
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 空间压缩
int rob(int *nums, int numsSize) {
    if (numsSize == 1)return nums[0];
    if (numsSize == 2)return max(nums[0], nums[1]);
    int left, mid, right;
    left = nums[0];
    mid = max(nums[0], nums[1]);
    for (int i = 2; i < numsSize; ++i) {
        right = max(mid, max(nums[i], left + nums[i]));
        left = mid;
        mid = right;
    }

    return right;
}

918. 环形子数组的最大和

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a > b ? b : a;
}

int maxSubarraySumCircular(int *nums, int numsSize) {
    // 普通数组的最大累加和
    int maxSum = nums[0];
    // 普通数组的最小累加和
    int minSum = nums[0];
    // 数组总和
    int sum = nums[0];
    int maxPre = nums[0], minPre = nums[0];
    // 环形数组的最大累加和，分为两类
    // 1.子数组连续：返回普通数组的最大累加和maxSum
    // 2.子数组不连续：包含nums中最前一段和最后一段，等价于去掉中间一段，去掉的中间子数组累加和越小越好，返回sum-minSum
    for (int i = 1; i < numsSize; ++i) {
        sum += nums[i];
        // 计算最大累加和
        maxPre = max(nums[i], nums[i] + maxPre);
        maxSum = max(maxSum, maxPre);
        // 计算最小累加和
        minPre = min(nums[i], nums[i] + minPre);
        minSum = min(minSum, minPre);
    }

    // 返回的子数组要非空
    return sum == minSum ? maxSum : max(maxSum, sum - minSum);
}

213. 打家劫舍 II

int max(int a, int b) {
    return a > b ? a : b;
}

// 返回nums[start...end]上不含相邻元素的最大累加和
int best(int *nums, int start, int end) {
    if (start > end) return 0;
    if (start == end) return nums[start];
    if (start + 1 == end) return max(nums[start], nums[end]);
    // dp[i-2]
    int left = nums[start];
    // dp[i-1]
    int mid = max(nums[start], nums[start + 1]);
    // dp[i]
    int right;
    // 不选当前的，返回dp[i-1]
    // 选当前nums[i]，分为nums[i]是否是单独作为一个子数组
    for (int i = start + 2; i <= end; ++i) {
        right = max(mid, max(nums[i], nums[i] + left));
        left = mid;
        mid = right;
    }
    return right;
}

int rob(int *nums, int numsSize) {
    if (numsSize == 1) return nums[0];
    // 分为包含和不包含nums[0]两类
    return max(nums[0] + best(nums, 2, numsSize - 2), best(nums, 1, numsSize - 1));
}

2560. 打家劫舍 IV

int max(int a, int b) {
    return a > b ? a : b;
}

// 自底向上
// 返回能力为ability时能偷的最多房间数量
int mostRob(int *nums, int numsSize, int ability) {
    if (numsSize == 1) return nums[0] <= ability ? 1 : 0;
    if (numsSize == 2) return (nums[0] <= ability || nums[1] <= ability) ? 1 : 0;
    int dp[numsSize];
    dp[0] = nums[0] <= ability ? 1 : 0;
    dp[1] = (nums[0] <= ability || nums[1] <= ability) ? 1 : 0;
    // 分为偷不偷当前房屋两种情况
    for (int i = 2; i < numsSize; ++i)
        dp[i] = max(dp[i - 1], (nums[i] <= ability ? 1 : 0) + dp[i - 2]);
    return dp[numsSize - 1];
}

int minCapability(int *nums, int numsSize, int k) {
    // 能力上下限
    int left = nums[0];
    int right = nums[0];
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] < left) left = nums[i];
        if (nums[i] > right) right = nums[i];
    }

    int mid;
    // 找左边界
    while (left <= right) {
        mid = left + (right - left) / 2;
        int temp = mostRob(nums, numsSize, mid);
        if (temp >= k)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

// 空间压缩
// 返回能力为ability时能偷的最多房间数量
int mostRob(int *nums, int numsSize, int ability) {
    if (numsSize == 1) return nums[0] <= ability ? 1 : 0;
    if (numsSize == 2) return (nums[0] <= ability || nums[1] <= ability) ? 1 : 0;
    int left = nums[0] <= ability ? 1 : 0;
    int mid = (nums[0] <= ability || nums[1] <= ability) ? 1 : 0;
    int right;
    // 分为偷不偷当前房屋两种情况
    for (int i = 2; i < numsSize; ++i) {
        right = max(mid, (nums[i] <= ability ? 1 : 0) + left);
        left = mid;
        mid = right;
    }
    return right;
}       

// 贪心
int mostRob(int *nums, int numsSize, int ability) {
    int res = 0;
    int i = 0;
    while (i < numsSize) {
        // 每个能偷的地方收益都是加1，所以尽早偷，让后面的范围更大
        if (nums[i] <= ability) {
            res++;
            // 跳到下下个位置
            i += 2;
        } else {
            i++;
        }
    }
    return res;
}

面试题 17.24. 最大子矩阵

int *getMaxMatrix(int **matrix, int matrixSize, int *matrixColSize, int *returnSize) {
    int rowSize = matrixSize;
    int columnSize = *matrixColSize;
    int *res = (int *) calloc(4, sizeof(int));
    *returnSize = 4;
    int maxSum = 0x80000000;
    // 每个元素表示子矩阵中同一列上多行元素的累加和
    int arr[columnSize];
    // 处理每个子矩阵
    for (int up = 0; up < rowSize; ++up) {
        // 清空临时数组
        memset(arr, 0, sizeof(int) * columnSize);
        for (int down = up; down < rowSize; ++down) {
            // 找最大累加和子数组的开始和结束位置
            int tempSum = 0x80000000;
            int left = 0;
            // 必须以arr[right]结尾，分为两种情况
            for (int right = 0; right < columnSize; ++right) {
                // 累加到临时数组中
                arr[right] += matrix[down][right];
                if (tempSum >= 0) {
                    // 情况1：前面的累加和是正数，则算上之前的
                    tempSum += arr[right];
                } else {
                    // 情况2：前面累加和是负数，则当前元素单独算作一个子数组
                    tempSum = arr[right];
                    // 更新子数组的起始位置
                    left = right;
                }
                if (tempSum > maxSum) {
                    maxSum = tempSum;
                    res[0] = up;
                    res[1] = left;
                    res[2] = down;
                    res[3] = right;
                }
            }
        }
    }

    return res;
}