子数组最大累加和
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 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
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
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 = 0) {
cur = pre + nums[right];
} else {
cur = nums[right];
left = right;
}
res = max(cur, res);
pre = cur;
}
printf("left=%d right=%dn", 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
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
- 以下写法允许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
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
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
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
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] right) right = nums[i];
}
int mid;
// 找左边界
while (left = 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]
// 贪心
int mostRob(int *nums, int numsSize, int ability) {
int res = 0;
int i = 0;
while (i
面试题 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 = 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;
}
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net