来自给定数组的第一个总和为负的子数组
原文：https://www.geeksforgeeks.org/first-subarray-with-negative-sum-from-the-given-array/
给定由N个整数组成的数组arr[]，任务是找到第一个子数组的起始索引和结尾索引为负数。 如果不存在这样的子数组，则打印 -1。
注意：如果给定数组中有多个负和子数组，则第一个子数组是指起始索引最低的子数组。
示例：
输入：
arr[] = {3, 3, -4, -2}输出：
1 2说明：
具有负和的第一个子数组是从索引 1 到索引 2，即
arr[1] + arr[2] = -1。输入：
arr[] = {1, 2, 3, 10}输出：-1
说明：
不存在负和的子数组。
朴素方法：朴素方法是从数组中从左到右生成所有子数组，并检查这些子数组中的任何一个是否具有负和。 如果是，则打印该子数组的开始和结束索引。
*时间复杂度：O(N ^ 2)。
辅助空间：O(1)*
-
遍历数组，对于第
i个索引（其中i的范围为[0, N – 1]），检查第i个索引的元素是否为负。 如果是这样，则arr[i]是所需的子数组。 -
否则，找到一个从
i + 1开始的索引，其中前缀和小于前缀和，直到i。 -
如果在上述步骤中找到任何这样的索引，则来自索引
{i, index}的子数组将给出第一个负子数组。 -
如果找不到这样的子数组，则打印 -1。 否则，打印获得的子数组。
下面是上述方法的实现：
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a sum less
// than pre_sum is present
int b_search(int pre_sum,
map<int, vector<int> >& m,
int index)
{
// Returns an iterator either equal
// to given key or next greater
auto it = m.lower_bound(pre_sum);
if (it == m.begin())
return -1;
// Decrement the iterator
it--;
// Check if the sum found at
// a greater index
auto it1
= lower_bound(it->second.begin(),
it->second.end(),
index);
if (*it1 > index)
return *it1;
return -1;
}
// Function to return the index
// of first negative subarray sum
vector<int> findSubarray(int arr[], int n)
{
// Stores the prefix sum- index
// mappings
map<int, vector<int> > m;
int sum = 0;
// Stores the prefix sum of
// the original array
int prefix_sum[n];
for (int i = 0; i < n; i++) {
sum += arr[i];
// Check if we get sum negative
// starting from first element
if (sum < 0)
return { 0, i };
prefix_sum[i] = sum;
m[sum].push_back(i);
}
// Iterate through array find
// the sum which is just less
// then the previous prefix sum
for (int i = 1; i < n; i++) {
// Check if the starting element
// is itself negative
if (arr[i] < 0)
// arr[i] becomes the required
// subarray
return { i, i };
else {
int pre_sum = prefix_sum[i - 1];
// Find the index which forms
// negative sum subarray
// from i-th index
int index = b_search(pre_sum,
m, i);
// If a subarray is found
// starting from i-th index
if (index != -1)
return { i, index };
}
}
// Return -1 if no such
// subarray is present
return { -1 };
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, -1, 3, -4, 3, -5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
vector<int> res = findSubarray(arr, n);
// If subarray does not exist
if (res[0] == -1)
cout << "-1" << endl;
// If the subarray exists
else {
cout << res[0]
<< " " << res[1];
}
return 0;
}
输出：
0 6
时间复杂度：O(N * log N)。
辅助空间：O(n)。
版权属于：月萌API www.moonapi.com，转载请注明出处
