資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中給定範圍內的最大字首和
問題陳述
給定一個包含n個整數的陣列和q個查詢，每個查詢都有一個從l到r的範圍。找到l-r範圍內的最大字首和。
示例
If input array is arr[] = {-1, 2, 3, -5} and
queries = 2 and ranges are:
l = 0, r = 3
l = 1, r = 3 then output will be 4 and 5.- 第一個查詢中的範圍(0, 3)為[-1, 2, 3, -5]，因為它是字首，所以我們必須從-1開始。因此，最大字首和將為-1 + 2 + 3 = 4
- 第二個查詢中的範圍(1, 3)為[2, 3, -5]，因為它是字首，所以我們必須從2開始。因此，最大字首和將為2 + 3 = 5
演算法
- 構建一個線段樹，其中每個節點儲存兩個值s（和和字首和），並在其上執行範圍查詢以找到最大字首和。
- 為了找出最大字首和，我們需要兩件事，一個是和，另一個是字首和
- 合併將返回兩件事，範圍的和以及將線上段樹中儲存max(prefix.left, prefix.sum + prefix.right)的字首和
- 任何兩個範圍組合的最大字首和將是左側的字首和或左側的和+右側的字首和，取其中較大的一個。
示例
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int sum;
int prefix;
} node;
node tree[4 * 10000];
void build(int *arr, int idx, int start, int end) {
if (start == end) {
tree[idx].sum = arr[start];
tree[idx].prefix = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2 * idx + 1, start, mid);
build(arr, 2 * idx + 2, mid + 1, end);
tree[idx].sum = tree[2 * idx + 1].sum + tree[2 *
idx + 2].sum;
tree[idx].prefix = max(tree[2 * idx + 1].prefix,
tree[2 * idx + 1].sum + tree[2 * idx + 2].prefix);
}
}
node query(int idx, int start, int end, int l, int r) {
node result;
result.sum = result.prefix = -1;
if (start > r || end < l) {
return result;
}
if (start >= l && end <= r) {
return tree[idx];
}
int mid = (start + end) / 2;
if (l > mid) {
return query(2 * idx + 2, mid + 1, end, l, r);
}
if (r <= mid) {
return query(2 * idx + 1, start, mid, l, r);
}
node left = query(2 * idx + 1, start, mid, l, r);
node right = query(2 * idx + 2, mid + 1, end, l, r);
result.sum = left.sum + right.sum;
result.prefix = max(left.prefix, left.sum + right.prefix);
return result;
}
int main() {
int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
build(arr, 0, 0, n - 1);
cout << "Result = " << query(0, 0, n - 1, 3, 5).prefix
<< endl;
return 0;
}輸出
編譯並執行上述程式時，會生成以下輸出：
Result = -1
更新於: 2020年1月21日
607 次瀏覽
廣告