Gəlir#2585

Gəlir (Həll təhlili)

Məsələdə, verilmiş bütün ardıcıl sıralanmış ədədlər arasında maksimum cəmi olan bir alt ardıcıllığı tapmaq lazımdır. Əgər $x_{i}, x_{i + 1}, ..., x_{j}$ x_i, x_{i+1}, ..., x_j alt ardıcıllığında maksimum cəm əldə edilərsə, o zaman hər hansı $k, 1 \leq k < i$ k, 1 \le k < i və $l, j < l \leq n$ l, j < l \le n üçün $x_{k}, ..., x_{i - 1}$ x_k, ..., x_{i-1} və $x_{j + 1}, ..., x_{l}$ x_{j+1}, ..., x_l ədədlərinin cəmi mənfi olacaqdır.

Kadanın Alqoritmi. Massivdə soldan sağa doğru hərəkət edirik və $s$ dəyişənində cari hissə cəmini toplayırıq. S hər hansı bir anda mənfi olarsa, onu $s = 0$ s = 0 olaraq təyin edirik. Massiv üzrə keçid zamanı $s$ dəyişəninin bütün qiymətlərinin maksimumu məsələnin cavabı olacaqdır.

Misal

Giriş ardıcıllığı üçün maksimum gəlir $14$ -ə bərabərdir.

Misal ardıcıllığını $X$ nəzərdən keçirək. Hissə cəmləri qururuq. Cari hissə cəmi mənfi olduqda cəm sıfırlayırıq və növbəti ədəddən etibarən cəmi hesablamağa başlayırıq. Bütün hissə cəmləri içində maksimum qiymət $6$ -ya bərabərdir ki, bu da cavabdır. Axtarılan alt ardıcıllıq $4, - 2, 4$ 4, -2, 4 olacaqdır.

Alqoritmin Təminatı

Ardıcıllığın uzunluğunu $n$ oxuyuruq. Maksimum gəlirin $ma x$ və cari hissə cəminin $s$ qiymətini sıfırlayırıq.

scanf("%d",&n);
s = 0; max = 0;

$n$ ədəd oxuyuruq. Hər oxunan $N u mb er$ ədədini cari cəm $s$ -ə əlavə edirik və cari gəlirin $ma x$ qiymətini yenidən hesablayırıq. Əgər hər hansı bir addımda $s$ dəyəri mənfiyə çevrilərsə, onu sıfır olaraq təyin edirik və prosesi davam etdiririk.

for(i = 0; i < n; i++)
{
  scanf("%d",&Number);
  s += Number;
  if (s > max) max = s;
  if (s < 0) s = 0;
}

C++

Nəticəni çıxara bilirik.

printf("%d\n",max);

Java Təminatı

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();

    int s = 0, max = 0;
    for (int i = 0; i < n; i++)
    {
      int val = con.nextInt();
      s += val;
      if (s > max) max = s;
      if (s < 0) s = 0;
    }
    
    System.out.println(max);
    con.close();
  }
}

Java

Python Təminatı

Ardıcıllığın uzunluğunu $n$ oxuyuruq. Maksimum gəlirin $ma x_p r o f i t$ max\_profit və cari hissə cəminin $s$ qiymətini sıfırlayırıq.

n = int(input())
s = 0
max_profit = 0

$n$ ədəd oxuyuruq. Hər oxunan $N u mb er$ ədədini cari cəm $s$ -ə əlavə edirik və cari gəlirin $ma x_p r o f i t$ max\_profit qiymətini yenidən hesablayırıq. Əgər hər hansı bir addımda $s$ dəyəri mənfiyə çevrilərsə, onu sıfır olaraq təyin edirik və prosesi davam etdiririk.

for i in range(n):
  Number = int(input())
  s += Number
  if s > max_profit: max_profit = s
  if s < 0: s = 0

Nəticəni çıxara bilirik.

print(max_profit)