子数组最大累加和
2024-02-07 17:38 由
Sprinining 发表于
#其他
子数组最大累加和
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;
}
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;
}
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;
}
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);
}
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));
}
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;
}
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;
}
热门相关：北宋大表哥 锦衣 娇妻如云 护花猎王 资本大唐