给定一个包含 N 整数。问题是找到具有最小和的相邻子阵列的元素之和。 例如：
null
Input : arr[] = {3, -4, 2, -3, -1, 7, -5}Output : -6Subarray is {-4, 2, -3, -1} = -6Input : arr = {2, 6, 8, 1, 4}Output : 1
天真的方法： 考虑不同大小的邻接子数组并找到它们的和。具有最小和的子阵列是必需的答案。 有效方法： 这是一个寻找目标问题的变体 最大和邻接子阵 基于卡丹算法的思想。 算法：
smallestSumSubarr(arr, n) Initialize min_ending_here = INT_MAX Initialize min_so_far = INT_MAX for i = 0 to n-1 if min_ending_here > 0 min_ending_here = arr[i] else min_ending_here += arr[i] min_so_far = min(min_so_far, min_ending_here) return min_so_far
C++
// C++ implementation to find the smallest sum // contiguous subarray #include <bits/stdc++.h> using namespace std; // function to find the smallest sum contiguous subarray int smallestSumSubarr( int arr[], int n) { // to store the minimum value that is ending // up to the current index int min_ending_here = INT_MAX; // to store the minimum value encountered so far int min_so_far = INT_MAX; // traverse the array elements for ( int i=0; i<n; i++) { // if min_ending_here > 0, then it could not possibly // contribute to the minimum sum further if (min_ending_here > 0) min_ending_here = arr[i]; // else add the value arr[i] to min_ending_here else min_ending_here += arr[i]; // update min_so_far min_so_far = min(min_so_far, min_ending_here); } // required smallest sum contiguous subarray value return min_so_far; } // Driver program to test above int main() { int arr[] = {3, -4, 2, -3, -1, 7, -5}; int n = sizeof (arr) / sizeof (arr[0]); cout << "Smallest sum: " << smallestSumSubarr(arr, n); return 0; } |
JAVA
// Java implementation to find the smallest sum // contiguous subarray class GFG { // function to find the smallest sum contiguous // subarray static int smallestSumSubarr( int arr[], int n) { // to store the minimum value that is // ending up to the current index int min_ending_here = 2147483647 ; // to store the minimum value encountered // so far int min_so_far = 2147483647 ; // traverse the array elements for ( int i = 0 ; i < n; i++) { // if min_ending_here > 0, then it could // not possibly contribute to the // minimum sum further if (min_ending_here > 0 ) min_ending_here = arr[i]; // else add the value arr[i] to // min_ending_here else min_ending_here += arr[i]; // update min_so_far min_so_far = Math.min(min_so_far, min_ending_here); } // required smallest sum contiguous // subarray value return min_so_far; } // Driver method public static void main(String[] args) { int arr[] = { 3 , - 4 , 2 , - 3 , - 1 , 7 , - 5 }; int n = arr.length; System.out.print( "Smallest sum: " + smallestSumSubarr(arr, n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to find the smallest sum # contiguous subarray maxsize = int ( 1e9 + 7 ) # function to find the smallest sum # contiguous subarray def smallestSumSubarr(arr, n): # to store the minimum value that is ending # up to the current index min_ending_here = maxsize # to store the minimum value encountered so far min_so_far = maxsize # traverse the array elements for i in range (n): # if min_ending_here > 0, then it could not possibly # contribute to the minimum sum further if (min_ending_here > 0 ): min_ending_here = arr[i] # else add the value arr[i] to min_ending_here else : min_ending_here + = arr[i] # update min_so_far min_so_far = min (min_so_far, min_ending_here) # required smallest sum contiguous subarray value return min_so_far # Driver code arr = [ 3 , - 4 , 2 , - 3 , - 1 , 7 , - 5 ] n = len (arr) print ( "Smallest sum: " , smallestSumSubarr(arr, n)) # This code is contributed by Sachin Bisht |
C#
// C# implementation to find the // smallest sum contiguous subarray using System; class GFG { // function to find the smallest sum // contiguous subarray static int smallestSumSubarr( int [] arr, int n) { // to store the minimum value that is // ending up to the current index int min_ending_here = 2147483647; // to store the minimum value encountered // so far int min_so_far = 2147483647; // traverse the array elements for ( int i = 0; i < n; i++) { // if min_ending_here > 0, then it could // not possibly contribute to the // minimum sum further if (min_ending_here > 0) min_ending_here = arr[i]; // else add the value arr[i] to // min_ending_here else min_ending_here += arr[i]; // update min_so_far min_so_far = Math.Min(min_so_far, min_ending_here); } // required smallest sum contiguous // subarray value return min_so_far; } // Driver method public static void Main() { int [] arr = { 3, -4, 2, -3, -1, 7, -5 }; int n = arr.Length; Console.Write( "Smallest sum: " + smallestSumSubarr(arr, n)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation to find the // smallest sum contiguous subarray // function to find the smallest // sum contiguous subarray function smallestSumSubarr( $arr , $n ) { // to store the minimum // value that is ending // up to the current index $min_ending_here = 999999; // to store the minimum value // encountered so far $min_so_far = 999999; // traverse the array elements for ( $i = 0; $i < $n ; $i ++) { // if min_ending_here > 0, // then it could not possibly // contribute to the minimum // sum further if ( $min_ending_here > 0) $min_ending_here = $arr [ $i ]; // else add the value arr[i] // to min_ending_here else $min_ending_here += $arr [ $i ]; // update min_so_far $min_so_far = min( $min_so_far , $min_ending_here ); } // required smallest sum // contiguous subarray value return $min_so_far ; } // Driver Code $arr = array (3, -4, 2, -3, -1, 7, -5); $n = count ( $arr ) ; echo "Smallest sum: " .smallestSumSubarr( $arr , $n ); // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript implementation to find the // smallest sum contiguous subarray // function to find the smallest sum // contiguous subarray function smallestSumSubarr(arr, n) { // to store the minimum value that is // ending up to the current index let min_ending_here = 2147483647; // to store the minimum value encountered // so far let min_so_far = 2147483647; // traverse the array elements for (let i = 0; i < n; i++) { // if min_ending_here > 0, then it could // not possibly contribute to the // minimum sum further if (min_ending_here > 0) min_ending_here = arr[i]; // else add the value arr[i] to // min_ending_here else min_ending_here += arr[i]; // update min_so_far min_so_far = Math.min(min_so_far, min_ending_here); } // required smallest sum contiguous // subarray value return min_so_far; } let arr = [ 3, -4, 2, -3, -1, 7, -5 ]; let n = arr.length; document.write( "Smallest sum: " + smallestSumSubarr(arr, n)); </script> |
输出：
Smallest sum: -6
时间复杂度：O（n） 本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
