合計が最大のサブアレイのサイズ


難易度 簡単に
よく聞かれる Coursera GreyOrange UHGオプタム ゾーメ
配列 動的計画法

問題文

あなたは与えられます 配列 整数の。 指定された配列には、正の数と負の数の両方を含めることができます。 合計が最大のサブアレイのサイズを調べます。

arr[] = {1,4,-2,-5,2-1,4,3}
4

説明:2 -1 + 4 + 3 = 8は長さ4の最大合計です


arr[] = {2,-4,1,2,-3,-4}
2

説明:1 + 2 = 3は長さ2の最大合計です

アルゴリズム

1. Set the maxVal to the minimum value of an integer and maxPoint to 0, start, end, and s to 0.
2. Starting from i=0 to i<size(length of the array).
  1. Sum up the value of maximumPoint and arr[i] and store into the maximumPoint.
  2. Check if maxVal is less than maxPoint, then update the following:
    maxVal = maxPoint
    start=s
    nd=i
  3. Check if the maximumPoint is less than 0, then update
    maximumPoint=0
    s=i+1
3. Return the value (end – start + 1).

最大合計でサブアレイのサイズを計算するための説明

整数の配列が与えられます。 私たちの仕事は、の長さを見つけることです 最大の合計を持つサブアレイ。 負の整数と正の整数を含めることもできます。 わたしたちは・・・にいくつもりです トラバース 展示はXNUMX回だけで、その後はO(n)の時間計算量になります。 を見つけます 最大 線形時間計算量のサブ値の合計。

次のような変数の特定の値を設定します 最大値 の最小値に 整数, 最大ポイント 0に、そして start, 終わり s 長さnまで配列のトラバースを開始します。 ループ内でiの値が増加するたびに、現在の配列要素を合計maxPointに含め、それをmaxPointに格納します。

maxValueの値を整数の最小値に設定し、maxValueがmaxPoint以下である可能性をチェックします。有効な場合は、その時点でmaxPointからmaxValueの値を更新します。 start to sの場合、この開始変数は連続するサブアレイの開始範囲の値を設定し、endがあります。これをiで更新します。

ここで、maxPointが0未満かどうかを確認します。これは、サブ配列の合計が負であることを意味します。その時点で、maxPointの値を0に、sをi + 1に再度更新します。これにより、「s」が開始範囲の値を設定するのに再び役立ち、最大の合計サブ配列を見つけるのに役立ちます。 このmaxPointは、最大の合計を見つける必要があるため、ゼロとして初期化し、その後、値をend-start +1として返します。 この戻り値は、最大合計の最大のサブ配列の長さになります。

最大合計のサブアレイのサイズ

最大合計でサブアレイのサイズを見つけるためのC ++での実装

#include<bits/stdc++.h>

using namespace std;

int getSizeMaxSum (int arr[], int size)
{
    int maxVal = INT_MIN, maximumPoint = 0,
        start =0, end = 0, s=0;

    for (int i=0; i< size; i++ )
    {
        maximumPoint += arr[i];

        if (maxVal < maximumPoint)
        {
            maxVal = maximumPoint;
            start = s;
            end = i;
        }

        if (maximumPoint < 0)
        {
            maximumPoint = 0;
            s = i + 1;
        }
    }

    return (end - start + 1);
}
int main()
{
    int arr[] = {1, -2, 1, 1, -2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getSizeMaxSum(arr, n);
    return 0;
}
2

 

最大合計のサブアレイのサイズのJavaでの実装

class SubArraySizeMaximumSum
{

    public static int getSizeMaxSum (int arr[], int size)
    {
        int maxVal = Integer.MIN_VALUE,
            maximumPoint = 0,start = 0,
            end = 0, s = 0;

        for (int i = 0; i < size; i++)
        {
            maximumPoint += arr[i];

            if (maxVal < maximumPoint)
            {
                maxVal = maximumPoint;
                start = s;
                end = i;
            }

            if (maximumPoint < 0)
            {
                maximumPoint = 0;
                s = i + 1;
            }
        }
        return (end - start + 1);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, -2, 1, 1, -2, 1};
        int n = arr.length;
        System.out.println(getSizeMaxSum(arr, n));
    }
}
2

複雑さの分析

時間の複雑さ

O(N) where 「n」 配列内の要素の数です。 配列をXNUMX回トラバースするためだけに単一のループを使用したため、線形時間計算量ソリューションになります。

スペースの複雑さ

O(N) where 「n」 配列内の要素の数です。 サイズnの単一の配列を使用したため、線形空間の複雑さもあります。