主页 / 问题 / 1538752
Accepted
Alexander
Asked:2023-09-02 15:42:48 +0000 UTC2023-09-02 15:42:48 +0000 UTC

给定金额有多少个子段？

  • 772

我有个问题。给定一个数字数组 a，其中 (-10^9 <= ai <= 10^9)。对于这个数字数组，你需要找到数组中和最大的子段，取出这个和以及这样的子段的数量。我设法找到了最大金额（我附上了代码），但我不太明白如何快速找到金额。如果您有任何想法，我将非常感激。

 int n;
 cin >> n;
 vector<int> a(n);
 for (int i = 0; i < n; ++i) cin >> a[i];

 int ans = a[0], sum = 0;
 for (int r = 0; r < n; ++r) {
      sum += a[r];
      ans = max(ans, sum);
      sum = max(sum, 0);
 }
 cout << ans;

unordered_map<int, int> check;
int s[n + 1];
for (int i = 0; i < n; i++) {
      s[i + 1] = s[i] + a[i];
       if (check.find(s[i + 1]) != check.end()) {
           ++check[s[i + 1]];
       } else {
          check[s[i + 1]] = 1;
       }
}
c++

1 个回答

  1. Best Answer

    计算累积和（从第一个元素到第 k 个元素的和）并将其添加到字典中。

    如果字典包含键 currentsum-best，则您已找到具有最佳总和的段。如果您将总和的数量存储在值中，您将获得分段的数量

    不使用语言特性的Python代码：

    a = [1,1,-3,3,-2,-1,2,-2,2,1]
cs = 0
res = 0
best = 3
dic = {0:1}
for x in a:
    cs += x

    if cs-best in dic:
        res += dic[cs-best]

    if cs in dic:
        dic[cs] = dic[cs]+1
    else:
        dic[cs] = 1
    print(cs)
print(dic)
print(res)

1 2 -1 2 0 -1 1 -1 1 2
{1: 3, 2: 3, -1: 3, 0: 2}
4
    • 1

相关问题