元素和为’k’的最长子阵列-yiteyi-C++库

给定一个整数数组，我们的目标是找到最大子数组的长度，其中k>0，其元素之和最多为’k’。

null

例如：

Input : arr[] = {1, 2, 1, 0, 1, 1, 0}, k = 4Output : 5Explanation: {1, 2, 1} => sum = 4, length = 3 {1, 2, 1, 0}, {2, 1, 0, 1} => sum = 4, length = 4 {1, 0, 1, 1, 0} =>5 sum = 3, length = 5

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法1（暴力） 找到其和小于或等于k的所有子数组，并返回长度最大的子数组。时间复杂度：O（n^2） 方法2（高效）： 一 有效的方法 就是使用滑动窗口技术 .

遍历数组，检查当前元素的和是否小于或等于k。
如果小于k，则将其添加到总和并增加计数。
跟踪最大计数。

C++

                         // A C++ program to find longest subarray with                       
                         // sum of elements at-least k.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to find the length of largest subarray                       
                         // having sum atmost k.                       
                         int                                     atMostSum(                                     int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     sum = 0;                       
                                                 int                                     cnt = 0, maxcnt = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                   
                                                 // If adding current element doesn't                       
                                                 // cross limit add it to current window                       
                                                 if                                     ((sum + arr[i]) <= k) {                       
                                                 sum += arr[i];                       
                                                 cnt++;                       
                                                 }                       
           
                                                 // Else, remove first element of current                       
                                                 // window and add the current element                       
                                                 else                                     if                                     (sum!=0)                       
                                                 {                       
                                                 sum = sum - arr[i - cnt] + arr[i];                       
                                                 }                       
           
                                                 // keep track of max length.                       
                                                 maxcnt = max(cnt, maxcnt);                       
                                                 }                       
                                                 return                                     maxcnt;                       
                         }                       
           
                         // Driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 2, 1, 0, 1, 1, 0};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     k = 4;                       
           
                                                 cout << atMostSum(arr, n, k);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find longest subarray with                       
                         // sum of elements at-least k.                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // function to find the length of largest                       
                                                 // subarray having sum atmost k.                       
                                                 public                                     static                                     int                                     atMostSum(                                     int                                     arr[],                                     int                                     n,                       
                                                 int                                     k)                       
                                                 {                       
                                                 int                                     sum =                                     0                                     ;                       
                                                 int                                     cnt =                                     0                                     , maxcnt =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                   
                                                 // If adding current element doesn't                       
                                                 // cross limit add it to current window                       
                                                 if                                     ((sum + arr[i]) <= k) {                       
                                                 sum += arr[i];                       
                                                 cnt++;                       
                                                 }                       
                                   
                                                 // Else, remove first element of current                       
                                                 // window.                       
                                                 else                                     if                                     (sum!=                                     0                                     )                       
                                                 {                       
                                                 sum = sum - arr[i - cnt] + arr[i];                       
                                                 }                       
                                   
                                                 // keep track of max length.                       
                                                 maxcnt = Math.max(cnt, maxcnt);                       
                                                 }                       
                                                 return                                     maxcnt;                       
                                                 }                       
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     1                                     ,                                     0                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     k =                                     4                                     ;                       
                                   
                                                 System.out.print(atMostSum(arr, n, k));                       
                                   
                                                 }                       
                         }                       
                         // This code is contributed by Arnav Kr. Mandal.                       

Python3

                         # Python3 program to find longest subarray                       
                         # with sum of elements at-least k.                       
           
                         # function to find the length of largest                       
                         # subarray having sum atmost k.                       
                         def                                     atMostSum(arr, n, k):                       
                                                 _sum                                     =                                     0                       
                                                 cnt                                     =                                     0                       
                                                 maxcnt                                     =                                     0                       
                                   
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 # If adding current element doesn't                       
                                                 # Cross limit add it to current window                       
                                                 if                                     ((_sum                                     +                                     arr[i]) <                                     =                                     k):                       
                                                 _sum                                     +                                     =                                     arr[i]                       
                                                 cnt                                     +                                     =                                     1                       
                                   
                                                 # Else, remove first element of current                       
                                                 # window and add the current element                       
                                                 elif                                     (                                     sum                                     !                                     =                                     0                                     ):                       
                                                 _sum                                     =                                     _sum                                     -                                     arr[i                                     -                                     cnt]                                     +                                     arr[i]                       
                                   
                                                 # keep track of max length.                       
                                                 maxcnt                                     =                                     max                                     (cnt, maxcnt)                       
           
                                                 return                                     maxcnt                       
                                   
                         # Driver function                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     1                                     ,                                     0                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         k                                     =                                     4                       
                         print                                     (atMostSum(arr, n, k))                       
           
                         # This code is contributed by "Abhishek Sharma 44"                       

C#

                         // C# program to find longest subarray                       
                         // with sum of elements at-least k.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // function to find the length of largest                       
                                                 // subarray having sum atmost k.                       
                                                 public                                     static                                     int                                     atMostSum(                                     int                                     []arr,                                     int                                     n,                       
                                                 int                                     k)                       
                                                 {                       
                                                 int                                     sum = 0;                       
                                                 int                                     cnt = 0, maxcnt = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                   
                                                 // If adding current element doesn't                       
                                                 // cross limit add it to current window                       
                                                 if                                     ((sum + arr[i]) <= k) {                       
                                                 sum += arr[i];                       
                                                 cnt++;                       
                                                 }                       
                                   
                                                 // Else, remove first element                       
                                                 // of current window.                       
                                                 else                                     if                                     (sum!=0)                       
                                                 {                       
                                                 sum = sum - arr[i - cnt] + arr[i];                       
                                                 }                       
                                   
                                                 // keep track of max length.                       
                                                 maxcnt = Math.Max(cnt, maxcnt);                       
                                                 }                       
                                                 return                                     maxcnt;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = {1, 2, 1, 0, 1, 1, 0};                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     k = 4;                       
                                   
                                                 Console.Write(atMostSum(arr, n, k));                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal                       

PHP

                         <?php                       
                         // A PHP program to find longest                       
                         // subarray with sum of elements                       
                         // at-least k.                       
           
                         // function to find the length                       
                         // of largest subarray having                       
                         // sum atmost k.                       
                         function                                     atMostSum(&                                     $arr                                     ,                                     $n                                     ,                                     $k                                     )                       
                         {                       
                                                 $sum                                     = 0;                       
                                                 $cnt                                     = 0;                       
                                                 $maxcnt                                     = 0;                       
           
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // If adding current element                       
                                                 // doesn't cross limit add                       
                                                 // it to current window                       
                                                 if                                     ((                                     $sum                                     +                                     $arr                                     [                                     $i                                     ]) <=                                     $k                                     )                       
                                                 {                       
                                                 $sum                                     +=                                     $arr                                     [                                     $i                                     ] ;                       
                                                 $cnt                                     += 1 ;                       
                                                 }                       
           
                                                 // Else, remove first element                       
                                                 // of current window and add                       
                                                 // the current element                       
                                                 else                                     if                                     (                                     $sum                                     != 0)                       
                                                 $sum                                     =                                     $sum                                     -                                     $arr                                     [                                     $i                                     -                                     $cnt                                     ] +                       
                                                 $arr                                     [                                     $i                                     ];                       
                                   
                                                 // keep track of max length.                       
                                                 $maxcnt                                     = max(                                     $cnt                                     ,                                     $maxcnt                                     );                       
                                                 }                       
                                                 return                                     $maxcnt                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 2, 1, 0, 1, 1, 0);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         $k                                     = 4;                       
           
                         print                                     (atMostSum(                                     $arr                                     ,                                     $n                                     ,                                     $k                                     ));                       
           
                         // This code is contributed                       
                         // by ChitraNayal                       
                         ?>                       

Javascript

                         <script>                       
                         // A Javascript program to find longest subarray with                       
                         // sum of elements at-least k.                       
           
                         // function to find the length of largest subarray                       
                         // having sum atmost k.                       
                         function                                     atMostSum(arr, n, k)                       
                         {                       
                                                 let sum = 0;                       
                                                 let cnt = 0, maxcnt = 0;                       
           
                                                 for                                     (let i = 0; i < n; i++) {                       
                                   
                                                 // If adding current element doesn't                       
                                                 // cross limit add it to current window                       
                                                 if                                     ((sum + arr[i]) <= k) {                       
                                                 sum += arr[i];                       
                                                 cnt++;                       
                                                 }                       
           
                                                 // Else, remove first element of current                       
                                                 // window and add the current element                       
                                                 else                                     if                                     (sum!=0)                       
                                                 {                       
                                                 sum = sum - arr[i - cnt] + arr[i];                       
                                                 }                       
           
                                                 // keep track of max length.                       
                                                 maxcnt = Math.max(cnt, maxcnt);                       
                                                 }                       
                                                 return                                     maxcnt;                       
                         }                       
           
                         // Driver function                       
                                                 let arr = [1, 2, 1, 0, 1, 1, 0];                       
                                                 let n = arr.length;                       
                                                 let k = 4;                       
           
                                                 document.write(atMostSum(arr, n, k));                       
           
                         </script>                       

输出：

时间复杂性 ：O（n）本文由 克希提兹·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章