Maksimum Cəmi Artıran Nəticə

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Atlassian Bloomberg ByteDance Citrix Kod milləti Kupanq eBay Facebook google IBM microsoft Nagarro Kahin Über Yahoo
Geyim İkili axtarış Dinamik proqramlaşdırmaBaxılıb 375

Problem bəyanat

“Maksimum cəmi artıran sonrakı nəticə” problemində bir array. Verilən massivin maksimum ardıcıllığının cəmini tapın, yəni ardıcıllıqdakı tam ədədlər sıralanmış qaydada.

Bir ardıcıllıq, sıra dəyişdirmədən bəzi elementləri silməklə başqa bir ardıcıllıqdan əldə edilən bir sıra olan bir sıra hissəsidir. Bunu aşağıdakı nümunədə izah etmək olar.

misal

4
18 5 17 23
45

Explanation: Yuxarıdakı nümunədə 45 maksimum cəmdir. Yuxarıdakı nümunədə artan iki ardıcıllıq var, yəni {18, 17} və {5, 17, 23}. Ancaq ikinci ardıcıllıq maksimum cəmə malikdir.

Yanaşma

Bir sıra müsbət ədədlər verilir. Dizinin maksimum cəmi ardıcıllığının cəmini elə hesablamalıyıq ki, ardıcıllıq artan_sıradadır. 

Məsələn -  [2,5,8,3,4,6]

O zaman bəzi artan ardıcıllıqlar - 

[2,5,8], cəmi = 15

[2,8], cəmi = 10

[5,8], cəmi = 13

[2,3,4,6], cəmi = 15

[2,5,6], cəmi = 13 s. Əldə etdiyimiz maksimum məbləğ 15-dir.

Problem sadə alt problemlərə bölünə bilər, yəni bunun var optimal alt quruluş. Həm də problem var üst-üstə düşən subroblemlər onun rekursiya ağacını çəksək. Problem optimal alt quruluşa və üst-üstə düşən alt problemlərə malik olduğundan problem istifadə edilərək həll edilə bilər dinamik proqramlaşdırma. A [0,1, …… n-1] bir sıra olsun və dp [i] = i indeksində sona çatan maksimum cəmi artan ardıcıllıq, belə ki, a [i] son ​​element olsun.

Sonra dp [i] kimi yazmaq olar, 

dp [i] = a [i] + max (L [j]) burada 0

Ans, 0 olduğu yerdə maks (dp [i]) olacaqdır

Yanaşma

  1. Dp [i] = a [i], burada 0 olduğu yeni bir dp massivi yaradacağıq
  2. 0 <i <n-dən xarici bir döngə aparacağıq.
  3. Maksimum cəmi artıran hər bir i üçün i ilə bitən bir [0, i-1] ardıcıllığı. A [j] ilə cari a [i] elementindən az olduğu bir [j] ilə bitən maksimum cəm ​​ilə artan ardıcıllıq.
  4. Dp massivində maksimumunu tapın.

Həyata keçirilməsi

Maksimum Cəmi Artıran Nəticə üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

int max_sum_inc_sub(vector<int> a,int n){
  vector<int> dp(a);
  int ans = 0;
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
        dp[i] = dp[j]+a[i];
      }
    }
    ans = max(ans,dp[i]);
  }
  return ans;
}
int main() {
  int n;
  cin>>n;
  vector<int> a;
  for(int i=0;i<n;i++){
    int x;cin>>x;
    a.push_back(x);
  }
  int max_sum = max_sum_inc_sub(a,n);
  cout<<max_sum<<endl;
  return 0;
}

Maksimum Cəmi Artıran Nəticə üçün Java Proqramı

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int ans = max_sum_inc_sub(arr,n);
        System.out.println(ans);
  }
  
  public static int max_sum_inc_sub(int[] a,int n){
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
        	dp[i]=a[i];
        }
        int ans = 0;
    for(int i=1;i<n;i++){
      for(int j=0;j<i;j++){
        if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
          dp[i] = dp[j]+a[i];
        }
      }
      ans = Math.max(ans,dp[i]);
    }
    return ans;
    }

}
6
2 5 8 3 4 6
15

Maksimum Cəmi Artıran Nəticə üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n * n) hara n verilmiş massivin ölçüsüdür. Burada bizi dördbucaqlı vaxt mürəkkəbliyinə aparan döngələr üçün iki yuva işlədirik.

Kosmik Mürəkkəblik

O (n) çünki 1 ölçülü bir sıra istifadə edirik. Burada dəyərləri xətti bir dp massivində saxlayırıq.

Translate »