# 算法题：最长子数组，元素总和不超过k

2021年4月20日14:56:42 发表评论 979 次浏览

## 本文概述

``````Input : arr[] = {1, 2, 1, 0, 1, 1, 0}, k = 4
Output : 5
Explanation:
{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``````

Else
删除子数组的第一个元素并减少计数。
再次检查在添加当前元素时, 其总和是否小于或等于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++) {

//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++) {

//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++) {

//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 ++)
{
//it to current window
if (( \$sum + \$arr [ \$i ]) <= \$k )
{
\$sum += \$arr [ \$i ] ;
\$cnt += 1 ;
}

//Else, remove first element
//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
?>``````

``5``