Given two binary arrays, arr1[] and arr2[] of the same size n. Find the length of the longest common span (i, j) where j >= i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j].
The expected time complexity is Θ(n).
Examples:
Input: arr1[] = {0, 1, 0, 0, 0, 0};
arr2[] = {1, 0, 1, 0, 0, 1};
Output: 4
The longest span with same sum is from index 1 to 4.
Input: arr1[] = {0, 1, 0, 1, 1, 1, 1};
arr2[] = {1, 1, 1, 1, 1, 0, 1};
Output: 6
The longest span with same sum is from index 1 to 6.
Input: arr1[] = {0, 0, 0};
arr2[] = {1, 1, 1};
Output: 0
Input: arr1[] = {0, 0, 1, 0};
arr2[] = {1, 1, 1, 1};
Output: 1
We strongly recommend that you click here and practice it, before moving on to the solution.
Method 1 (Simple Solution)
One by one by consider same subarrays of both arrays. For all subarrays, compute sums and if sums are same and current length is more than max length, then update max length. Below is C++ implementation of the simple approach.
C++
#include<bits/stdc++.h>
using namespace std;
int longestCommonSum(bool arr1[], bool arr2[], int n)
{
int maxLen = 0;
for (int i=0; i<n; i++)
{
int sum1 = 0, sum2 = 0;
for (int j=i; j<n; j++)
{
sum1 += arr1[j];
sum2 += arr2[j];
if (sum1 == sum2)
{
int len = j-i+1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}
int main()
{
bool arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof(arr1)/sizeof(arr1[0]);
cout << "Length of the longest common span with same "
"sum is "<< longestCommonSum(arr1, arr2, n);
return 0;
}
Java
class Test
{
static int arr1[] = new int[]{0, 1, 0, 1, 1, 1, 1};
static int arr2[] = new int[]{1, 1, 1, 1, 1, 0, 1};
static int longestCommonSum(int n)
{
int maxLen = 0;
for (int i=0; i<n; i++)
{
int sum1 = 0, sum2 = 0;
for (int j=i; j<n; j++)
{
sum1 += arr1[j];
sum2 += arr2[j];
if (sum1 == sum2)
{
int len = j-i+1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}
public static void main(String[] args)
{
System.out.print("Length of the longest common span with same sum is ");
System.out.println(longestCommonSum(arr1.length));
}
}
Python3
def longestCommonSum(arr1, arr2, n):
maxLen = 0
for i in range(0,n):
sum1 = 0
sum2 = 0
for j in range(i,n):
sum1 += arr1[j]
sum2 += arr2[j]
if (sum1 == sum2):
len = j-i+1
if (len > maxLen):
maxLen = len
return maxLen
arr1 = [0, 1, 0, 1, 1, 1, 1]
arr2 = [1, 1, 1, 1, 1, 0, 1]
n = len(arr1)
print("Length of the longest common span with same "
"sum is",longestCommonSum(arr1, arr2, n))
C#
using System;
class GFG
{
static int[] arr1 = new int[]{0, 1, 0, 1, 1, 1, 1};
static int[] arr2 = new int[]{1, 1, 1, 1, 1, 0, 1};
static int longestCommonSum(int n)
{
int maxLen = 0;
for (int i = 0; i < n; i++)
{
int sum1 = 0, sum2 = 0;
for (int j = i; j < n; j++)
{
sum1 += arr1[j];
sum2 += arr2[j];
if (sum1 == sum2)
{
int len = j - i + 1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}
public static void Main()
{
Console.Write("Length of the longest " +
"common span with same sum is ");
Console.Write(longestCommonSum(arr1.Length));
}
}
PHP
<?php
function longestCommonSum($arr1, $arr2, $n)
{
$maxLen = 0;
for ($i = 0; $i < $n; $i++)
{
$sum1 = 0; $sum2 = 0;
for ($j = $i; $j < $n; $j++)
{
$sum1 += $arr1[$j];
$sum2 += $arr2[$j];
if ($sum1 == $sum2)
{
$len = $j - $i + 1;
if ($len > $maxLen)
$maxLen = $len;
}
}
}
return $maxLen;
}
$arr1 = array(0, 1, 0, 1, 1, 1, 1);
$arr2 = array (1, 1, 1, 1, 1, 0, 1);
$n = sizeof($arr1);
echo "Length of the longest common span ".
"with same ", "sum is ",
longestCommonSum($arr1, $arr2, $n);
?>
Javascript
<script>
let arr1 = [0, 1, 0, 1, 1, 1, 1];
let arr2 = [1, 1, 1, 1, 1, 0, 1];
function longestCommonSum(n)
{
let maxLen = 0;
for (let i = 0; i < n; i++)
{
let sum1 = 0, sum2 = 0;
for (let j = i; j < n; j++)
{
sum1 += arr1[j];
sum2 += arr2[j];
if (sum1 == sum2)
{
let len = j - i + 1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}
document.write("Length of the longest " + "common span with same sum is ");
document.write(longestCommonSum(arr1.length));
</script>
Output :
Length of the longest common span with same sum is 6
Time Complexity : O(n2)
Auxiliary Space : O(1)
Method 2 (Using Auxiliary Array)
The idea is based on the below observations.
- Since there are total n elements, maximum sum is n for both arrays.
- The difference between two sums varies from -n to n. So there are total 2n + 1 possible values of difference.
- If differences between prefix sums of two arrays become same at two points, then subarrays between these two points have same sum.
Below is the Complete Algorithm.
- Create an auxiliary array of size 2n+1 to store starting points of all possible values of differences (Note that possible values of differences vary from -n to n, i.e., there are total 2n+1 possible values)
- Initialize starting points of all differences as -1.
- Initialize maxLen as 0 and prefix sums of both arrays as 0, preSum1 = 0, preSum2 = 0
- Traverse both arrays from i = 0 to n-1.
- Update prefix sums: preSum1 += arr1[i], preSum2 += arr2[i]
- Compute difference of current prefix sums: curr_diff = preSum1 – preSum2
- Find index in diff array: diffIndex = n + curr_diff // curr_diff can be negative and can go till -n
- If curr_diff is 0, then i+1 is maxLen so far
- Else If curr_diff is seen first time, i.e., starting point of current diff is -1, then update starting point as i
- Else (curr_diff is NOT seen first time), then consider i as ending point and find length of current same sum span. If this length is more, then update maxLen
- Return maxLen
Below is the implementation of above algorithm.
C++
#include<bits/stdc++.h>
using namespace std;
int longestCommonSum(bool arr1[], bool arr2[], int n)
{
int maxLen = 0;
int preSum1 = 0, preSum2 = 0;
int diff[2*n+1];
memset(diff, -1, sizeof(diff));
for (int i=0; i<n; i++)
{
preSum1 += arr1[i];
preSum2 += arr2[i];
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;
if (curr_diff == 0)
maxLen = i+1;
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;
else
{
int len = i - diff[diffIndex];
maxLen = max(maxLen,len);
}
}
return maxLen;
}
int main()
{
bool arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof(arr1)/sizeof(arr1[0]);
cout << "Length of the longest common span with same "
"sum is "<< longestCommonSum(arr1, arr2, n);
return 0;
}
Java
class Test
{
static int arr1[] = new int[]{0, 1, 0, 1, 1, 1, 1};
static int arr2[] = new int[]{1, 1, 1, 1, 1, 0, 1};
static int longestCommonSum(int n)
{
int maxLen = 0;
int preSum1 = 0, preSum2 = 0;
int diff[] = new int[2*n+1];
for (int i = 0; i < diff.length; i++) {
diff[i] = -1;
}
for (int i=0; i<n; i++)
{
preSum1 += arr1[i];
preSum2 += arr2[i];
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;
if (curr_diff == 0)
maxLen = i+1;
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;
else
{
int len = i - diff[diffIndex];
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}
public static void main(String[] args)
{
System.out.print("Length of the longest common span with same sum is ");
System.out.println(longestCommonSum(arr1.length));
}
}
Python
def longestCommonSum(arr1, arr2, n):
maxLen = 0
presum1 = presum2 = 0
diff = {}
for i in range(n):
presum1 += arr1[i]
presum2 += arr2[i]
curr_diff = presum1 - presum2
if curr_diff == 0:
maxLen = i+1
elif curr_diff not in diff:
diff[curr_diff] = i
else:
length = i - diff[curr_diff]
maxLen = max(maxLen, length)
return maxLen
arr1 = [0, 1, 0, 1, 1, 1, 1]
arr2 = [1, 1, 1, 1, 1, 0, 1]
print("Length of the longest common",
" span with same", end = " ")
print("sum is",longestCommonSum(arr1,
arr2, len(arr1)))
C#
using System;
class GFG
{
static int[] arr1 = new int[]{0, 1, 0, 1, 1, 1, 1};
static int[] arr2 = new int[]{1, 1, 1, 1, 1, 0, 1};
static int longestCommonSum(int n)
{
int maxLen = 0;
int preSum1 = 0, preSum2 = 0;
int[] diff = new int[2 * n + 1];
for (int i = 0; i < diff.Length; i++)
{
diff[i] = -1;
}
for (int i = 0; i < n; i++)
{
preSum1 += arr1[i];
preSum2 += arr2[i];
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;
if (curr_diff == 0)
maxLen = i + 1;
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;
else
{
int len = i - diff[diffIndex];
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}
public static void Main()
{
Console.Write("Length of the longest common " +
"span with same sum is ");
Console.WriteLine(longestCommonSum(arr1.Length));
}
}
Javascript
<script>
let arr1 = [0, 1, 0, 1, 1, 1, 1];
let arr2 = [1, 1, 1, 1, 1, 0, 1];
function longestCommonSum(n)
{
let maxLen = 0;
let preSum1 = 0, preSum2 = 0;
let diff = new Array(2 * n + 1);
for (let i = 0; i < diff.length; i++)
{
diff[i] = -1;
}
for (let i = 0; i < n; i++)
{
preSum1 += arr1[i];
preSum2 += arr2[i];
let curr_diff = preSum1 - preSum2;
let diffIndex = n + curr_diff;
if (curr_diff == 0)
maxLen = i + 1;
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;
else
{
let len = i - diff[diffIndex];
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}
document.write("Length of the longest common "
+ "span with same sum is ");
document.write(longestCommonSum(arr1.length));
</script>
Output:
Length of the longest common span with same sum is 6
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 3 (Using Hashing)
- Find difference array arr[] such that arr[i] = arr1[i] – arr2[i].
- Largest subarray with equal number of 0s and 1s in the difference array.
C++
#include <bits/stdc++.h>
using namespace std;
int longestCommonSum(bool arr1[], bool arr2[], int n)
{
int arr[n];
for (int i=0; i<n; i++)
arr[i] = arr1[i] - arr2[i];
unordered_map<int, int> hM;
int sum = 0;
int max_len = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
max_len = i + 1;
if (hM.find(sum) != hM.end())
max_len = max(max_len, i - hM[sum]);
else
hM[sum] = i;
}
return max_len;
}
int main()
{
bool arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof(arr1)/sizeof(arr1[0]);
cout << longestCommonSum(arr1, arr2, n);
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG
{
static int longestCommonSum(int[] arr1, int[] arr2, int n)
{
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = arr1[i] - arr2[i];
HashMap<Integer, Integer> hM = new HashMap<>();
int sum = 0;
int max_len = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
max_len = i + 1;
if (hM.containsKey(sum))
max_len = Math.max(max_len, i - hM.get(sum));
else
hM.put(sum, i);
}
return max_len;
}
public static void main(String args[])
{
int[] arr1 = {0, 1, 0, 1, 1, 1, 1};
int[] arr2 = {1, 1, 1, 1, 1, 0, 1};
int n = arr1.length;
System.out.println(longestCommonSum(arr1, arr2, n));
}
}
Python3
def longestCommonSum(arr1, arr2, n):
arr = [0 for i in range(n)]
for i in range(n):
arr[i] = arr1[i] - arr2[i];
hm = {}
sum = 0
max_len = 0
for i in range(n):
sum += arr[i]
if (sum == 0):
max_len = i + 1
if sum in hm:
max_len = max(max_len, i - hm[sum])
else:
hm[sum] = i
return max_len
arr1 = [0, 1, 0, 1, 1, 1, 1]
arr2 = [1, 1, 1, 1, 1, 0, 1]
n = len(arr1)
print(longestCommonSum(arr1, arr2, n))
C#
using System;
using System.Collections.Generic;
public class GFG
{
static int longestCommonSum(int[] arr1, int[] arr2, int n)
{
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = arr1[i] - arr2[i];
Dictionary<int,int> hM = new Dictionary<int,int>();
int sum = 0;
int max_len = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
max_len = i + 1;
if (hM.ContainsKey(sum))
max_len = Math.Max(max_len, i - hM[sum]);
else
hM[sum] = i;
}
return max_len;
}
static public void Main ()
{
int[] arr1 = {0, 1, 0, 1, 1, 1, 1};
int[] arr2 = {1, 1, 1, 1, 1, 0, 1};
int n = arr1.Length;
Console.WriteLine(longestCommonSum(arr1, arr2, n));
}
}
Javascript
<script>
function longestCommonSum(arr1,arr2,n)
{
let arr = new Array(n);
for (let i = 0; i < n; i++)
arr[i] = arr1[i] - arr2[i];
let hM = new Map();
let sum = 0;
let max_len = 0;
for (let i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
max_len = i + 1;
if (hM.has(sum))
max_len = Math.max(max_len, i - hM.get(sum));
else
hM.set(sum, i);
}
return max_len;
}
let arr1=[0, 1, 0, 1, 1, 1, 1];
let arr2=[1, 1, 1, 1, 1, 0, 1];
let n = arr1.length;
document.write(longestCommonSum(arr1, arr2, n));
</script>
Output:
6
Time Complexity: O(n) (As the array is traversed only once.)
Auxiliary Space: O(n) (As hashmap has been used which takes extra space.)
https://www.youtube.com/watch?v=xtfj4
-r_Ahs
This article is contributed by Sumit Gupta. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Last Updated :
27 Jan, 2023
Like Article
Save Article
Дан целочисленный массив, найдите в нем непрерывный подмассив с наибольшей суммой.
Например,
Input: {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Output: Subarray with the largest sum is {4, -1, 2, 1} with sum 6.
Потренируйтесь в этой проблеме
Задача отличается от задачи нахождения подпоследовательности максимальной суммы. В отличие от подпоследовательностей, подмассивы должны занимать последовательные позиции в исходном массиве.
Мы можем легко решить эту задачу за линейное время, используя Алгоритм Кадане. Идея состоит в том, чтобы поддерживать максимальный (с положительной суммой) подмассив, “заканчивающийся” на каждом индексе данного массива. Этот подмассив либо пуст (в этом случае его сумма равна нулю), либо состоит на один элемент больше, чем максимальный подмассив, оканчивающийся на предыдущем индексе.
Алгоритм может быть реализован следующим образом на C++, Java и Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <vector> using namespace std; // Функция для нахождения максимальной суммы непрерывного подмассива // в заданном целочисленном массиве int kadane(vector<int> const &arr) { // сохраняет максимальный суммарный подмассив, найденный на данный момент int max_so_far = 0; // сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции int max_ending_here = 0; // обход заданного массива for (int i = 0; i < arr.size(); i++) { // обновить максимальную сумму подмассива, «заканчивающегося» на индексе «i» (путем добавления // текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе ‘i-1’) max_ending_here = max_ending_here + arr[i]; // если максимальная сумма отрицательна, устанавливаем ее в 0 (что представляет // пустой подмассив) max_ending_here = max(max_ending_here, 0); // обновить результат, если текущая сумма подмассива окажется больше max_so_far = max(max_so_far, max_ending_here); } return max_so_far; } int main() { vector<int> arr = { —2, 1, —3, 4, —1, 2, 1, —5, 4 }; cout << «The maximum sum of a contiguous subarray is « << kadane(arr); return 0; } |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Main { // Функция для нахождения максимальной суммы непрерывного подмассива // в заданном целочисленном массиве public static int kadane(int[] arr) { // сохраняет максимальный суммарный подмассив, найденный на данный момент int maxSoFar = 0; // сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции int maxEndingHere = 0; // обход заданного массива for (int i: arr) { // обновить максимальную сумму подмассива, «заканчивающегося» на индексе «i» (путем добавления // текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе ‘i-1’) maxEndingHere = maxEndingHere + i; // если максимальная сумма отрицательна, устанавливаем ее в 0 (что представляет // пустой подмассив) maxEndingHere = Integer.max(maxEndingHere, 0); // обновить результат, если текущая сумма подмассива окажется больше maxSoFar = Integer.max(maxSoFar, maxEndingHere); } return maxSoFar; } public static void main(String[] args) { int[] arr = { —2, 1, —3, 4, —1, 2, 1, —5, 4 }; System.out.println(«The sum of contiguous subarray with the « + «largest sum is « + kadane(arr)); } } |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# Функция нахождения максимальной суммы непрерывного подмассива # в заданном целочисленном массиве def kadane(arr): # хранит подсписок максимальной суммы, найденный на данный момент. max_so_far = 0 # хранит максимальную сумму подсписков, заканчивающихся на текущей позиции max_ending_here = 0 # пройти по заданному списку for i in arr: # обновляет максимальную сумму подсписка, «заканчивающегося» на индексе «i» (путем добавления # текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе ‘i-1’) max_ending_here = max_ending_here + i #, если максимальная сумма отрицательна, установите ее на 0 (что означает # пустой подсписок) max_ending_here = max(max_ending_here, 0) # обновляет результат, если сумма текущего подсписка оказывается больше max_so_far = max(max_so_far, max_ending_here) return max_so_far if __name__ == ‘__main__’: arr = [—2, 1, —3, 4, —1, 2, 1, —5, 4] print(‘The sum of contiguous sublist with the largest sum is’, kadane(arr)) |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is 6
Временная сложность приведенного выше решения равна O(n) и не требует дополнительного места, где n это размер ввода.
Приведенный выше код не обрабатывает случай, когда все элементы массива отрицательные. Если массив содержит все отрицательные значения, ответом является максимальный элемент. Мы можем легко разместить эту проверку перед тем, как продолжить алгоритм. Реализацию можно увидеть ниже на C++, Java и Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Функция для нахождения максимальной суммы непрерывного подмассива // в заданном целочисленном массиве int kadane(vector<int> const &arr) { // находим максимальный элемент в заданном массиве int max_num = *max_element(arr.begin(), arr.end()); // если массив содержит все отрицательные значения, вернуть максимальный элемент if (max_num < 0) { return max_num; } // сохраняет максимальный суммарный подмассив, найденный на данный момент int max_so_far = 0; // сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции int max_ending_here = 0; // обход заданного массива for (int i = 0; i < arr.size(); i++) { // обновить максимальную сумму подмассива, «заканчивающегося» на индексе «i» (путем добавления // текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе ‘i-1’) max_ending_here = max_ending_here + arr[i]; // если максимальная сумма отрицательна, устанавливаем ее в 0 (что представляет // пустой подмассив) max_ending_here = max(max_ending_here, 0); // обновить результат, если текущая сумма подмассива окажется больше max_so_far = max(max_so_far, max_ending_here); } return max_so_far; } int main() { vector<int> arr = { —8, —3, —6, —2, —5, —4 }; cout << «The maximum sum of a contiguous subarray is « << kadane(arr); return 0; } |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is -2
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.Arrays; class Main { // Функция для нахождения максимальной суммы непрерывного подмассива // в заданном целочисленном массиве public static int kadane(int[] arr) { // находим максимальный элемент в заданном массиве int max = Arrays.stream(arr).max().getAsInt(); // если массив содержит все отрицательные значения, вернуть максимальный элемент if (max < 0) { return max; } // сохраняет максимальный суммарный подмассив, найденный на данный момент int maxSoFar = 0; // сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции int maxEndingHere = 0; // делаем для каждого элемента заданного массива for (int i: arr) { // обновить максимальную сумму подмассива, «заканчивающегося» на индексе «i» (путем добавления // текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе ‘i-1’) maxEndingHere = maxEndingHere + i; // если максимальная сумма отрицательна, устанавливаем ее в 0 (что представляет // пустой подмассив) maxEndingHere = Integer.max(maxEndingHere, 0); // обновить результат, если текущая сумма подмассива окажется больше maxSoFar = Integer.max(maxSoFar, maxEndingHere); } return maxSoFar; } public static void main(String[] args) { int[] arr = { —8, —3, —6, —2, —5, —4 }; System.out.println(«The sum of contiguous subarray with the « + «largest sum is « + kadane(arr)); } } |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is -2
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
# Функция нахождения максимальной суммы непрерывного подмассива # в заданном целочисленном массиве def kadane(arr): # найти максимальный элемент, присутствующий в данном списке maximum = max(arr) #, если список содержит все отрицательные значения, вернуть максимальный элемент if maximum < 0: return maximum # хранит подсписок максимальной суммы, найденный на данный момент. max_so_far = 0 # хранит максимальную сумму подсписков, заканчивающихся на текущей позиции max_ending_here = 0 # сделать для каждого элемента заданного списка for i in arr: # обновляет максимальную сумму подсписка, «заканчивающегося» на индексе «i» (путем добавления # текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе ‘i-1’) max_ending_here = max_ending_here + i #, если максимальная сумма отрицательна, установите ее на 0 (что означает # пустой подсписок) max_ending_here = max(max_ending_here, 0) # обновляет результат, если сумма текущего подсписка оказывается больше max_so_far = max(max_so_far, max_ending_here) return max_so_far if __name__ == ‘__main__’: arr = [—8, —3, —6, —2, —5, —4] print(‘The sum of contiguous sublist with the largest sum is’, kadane(arr)) |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is -2
Этот подход требует двух обходов входного массива. Мы можем легко модифицировать основной алгоритм, чтобы он обрабатывал и отрицательные целые числа. Алгоритм может быть реализован следующим образом на C++, Java и Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <vector> #include <climits> using namespace std; // Функция для нахождения максимальной суммы непрерывного подмассива // в заданном целочисленном массиве (также обрабатывает отрицательные числа) int kadaneNeg(vector<int> const &arr) { // сохраняет максимальный суммарный подмассив, найденный на данный момент int max_so_far = INT_MIN; // сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции int max_ending_here = 0; // обход заданного массива for (int i = 1; i < arr.size(); i++) { // обновить максимальную сумму подмассива, «заканчивающегося» на индексе «i» (путем добавления // текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе ‘i-1’) max_ending_here = max_ending_here + arr[i]; // максимальная сумма должна быть больше текущего элемента max_ending_here = max(max_ending_here, arr[i]); // обновить результат, если текущая сумма подмассива окажется больше max_so_far = max(max_so_far, max_ending_here); } return max_so_far; } int main() { vector<int> arr = { —8, —3, —6, —2, —5, —4 }; cout << «The maximum sum of a contiguous subarray is « << kadaneNeg(arr); return 0; } |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is -2
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
class Main { // Функция для нахождения максимальной суммы непрерывного подмассива // в заданном целочисленном массиве (также обрабатывает отрицательные числа) public static int kadaneNeg(int[] arr) { // сохраняет максимальный суммарный подмассив, найденный на данный момент int maxSoFar = Integer.MIN_VALUE; // сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции int maxEndingHere = 0; // обход заданного массива for (int i: arr) { // обновить максимальную сумму подмассива, «заканчивающегося» на индексе «i» (путем добавления // текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе) maxEndingHere = maxEndingHere + i; // максимальная сумма должна быть больше текущего элемента maxEndingHere = Integer.max(maxEndingHere, i); // обновить результат, если текущая сумма подмассива окажется больше maxSoFar = Integer.max(maxSoFar, maxEndingHere); } return maxSoFar; } public static void main(String[] args) { int[] arr = { —8, —3, —6, —2, —5, —4 }; System.out.println(«The maximum sum of a contiguous subarray is « + kadaneNeg(arr)); } } |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is -2
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import sys # Функция нахождения максимальной суммы непрерывного подмассива # в заданном целочисленном массиве (также обрабатывает отрицательные числа) def kadaneNeg(arr): # хранит подсписок максимальной суммы, найденный на данный момент. max_so_far = —sys.maxsize # хранит максимальную сумму подсписков, заканчивающихся на текущей позиции max_ending_here = 0 # пройти по заданному списку for i in range(len(arr)): # обновляет максимальную сумму подсписка, «заканчивающегося» на индексе «i» (путем добавления # текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе ‘i-1’) max_ending_here = max_ending_here + arr[i] # Максимальная сумма # должна быть больше, чем текущий элемент max_ending_here = max(max_ending_here, arr[i]) # обновляет результат, если сумма текущего подсписка оказывается больше max_so_far = max(max_so_far, max_ending_here) return max_so_far if __name__ == ‘__main__’: arr = [—8, —3, —6, —2, —5, —4] print(‘The sum of contiguous sublist with the largest sum is’, kadaneNeg(arr)) |
Скачать Выполнить код
результат:
The maximum sum of a contiguous subarray is -2
Из-за того, как этот алгоритм использует оптимальные основания (максимальный подмассив, заканчивающийся в каждой позиции, вычисляется просто из связанной, но меньшей и перекрывающейся подзадачи: максимальный подмассив, заканчивающийся в предыдущей позиции), этот алгоритм можно рассматривать как простой пример динамическое программирование.
Связанный пост:
Вывести непрерывный подмассив с максимальной суммой
Использованная литература: https://en.wikipedia.org/wiki/Maximum_subarray_problem
-
-
April 26 2009, 20:17
поиск отрезка в массиве
задача:
в заданном массиве целых чисел за один его просмотр, имея память константу, найти отрезок с максимальной суммой.
помогите, какой тут может быть алгоритм?
Предполагаю, что в массиве только положительные числа. Конечно можно и с отрицательными сделать аналогичную идею, но реализация значительно сложнее.
Эта задача решается с помощью скользящего окна. Общая идея — если у нас есть отрезок, сумма на котором меньше нужной, то убрав 1 элемент она по прежнему будет меньше нужной.
Используем это примерно в таком коде (псевдо С++):
@input vector<unsigned int> list, int K
@return {L,R}
int sum =0;
unsigend int l = 0, r = 0;
pair res = {-1,-1}
while (true){
if (r == list.size)
return res;
if (sum > K)
sum -= list[l++];
if (sum < K)
sum += list[r++];
if (sum == K)
if (res.second - res.first < r - l + 1)
res = {l,r+1};
}
Корректность:
Конечность: Мы каждую итерацию цикла сдвигаем либо l либо r указатель, l всегда не больше чем r. Поэтому цикл сделает не более 2*size операций.
Правильность: Если у нас сумма на отрезке меньше нужного, то добирать можно только справа (и мы обязаны это делать). Аналогично если меньше то мы обязаны убирать левый элемент. Если у нас сумма стала больше, то добавляя другие элементы справа мы её меньше не сделаем, аналогично если сумма меньше то удалять дальше смысла нет.
Остальное доказывается тривиально.
P.S. во многих алгоритмах правую границу отрезка удобнее не включать в сам отрезок. Т.е. использовать полуинтервал [a,b).
Эта, на сегодняшний день простая задача была представлена студентам и школьникам для поступления на работу в Яндекс 2011 года, узнайте справились бы вы.
Дан массив целых чисел. Найти отрезок этого массива с максимальной суммой.
Входные данные В первой строке дано натуральное число n ( 1 ≤ n ≤ 10e5 ) — размер массива. Во второй строке через пробел перечислены элемента массива. Числа не превышают 10e4 .
Выходные данные Выведите три числа — индекс начала отрезка, индекс конца и саму максимальную сумму. Массив индексируется с единицы. Если ответов несколько — выведите любой.
5
-1 2 3 -2 5
2 5 8