Mənfəəti artırmaq üçün səhmdar sat

Problem bəyanat

"Mənfəəti artırmaq üçün Satışa Satış" problemində verdik array hər gün stok qiymətini ehtiva edən, o günlərdə alqı-satqı ilə qazana biləcəyiniz maksimum qazancı tapın. Burada dəfələrlə alqı-satqı edə bilərik, ancaq bir səhm satdıqdan sonra başqa bir səhm ala bilərsiniz.

Giriş Formatı

Bir n tam ədədi olan ilk sətir.

Boşluqla ayrılmış n tam ədədi ehtiva edən ikinci sətir.

Çıxış formatı

Əldə edə biləcəyimiz maksimum mənfəəti göstərən bir ədədi çap edin. İstədiyiniz qədər əməliyyatı tamamlaya bilərsiniz (yəni bir hissə almaq və bir hissəni bir neçə dəfə satmaq).

misal

6
7 1 5 3 6 4

7

Explanation: 2-ci gündə alın (qiymət = 1) və 3-cü gündə satın (qiymət = 5), mənfəət = 5-1 = 4. Sonra 4-cü gündə (qiymət = 3) alıb 5-ci gündə (qiymət = 6) satın, mənfəət = 6-3 = 3.

Mənfəəti artırmaq üçün Satış Alqoritmi Satış

Bu vəziyyətdə, bir vadinin ardınca gələn hər zirvəni axtarmaq əvəzinə, yamacın üstündə sürünərək davam edən hər bir əməliyyatdan əldə olunan mənfəəti əlavə etməyə davam edə bilərik. Sonda zirvələri və vadilərdən səmərəli istifadə edəcəyik, ancaq zirvələrə və vadilərə uyğun olan xərcləri maksimum qazancla birlikdə izləməyimiz lazım deyil, ancaq birbaşa ardıcıl nömrələr arasındakı fərqi əlavə etməyə davam edə bilərik. ikinci nömrə birincidən daha böyükdür və əldə etdiyimiz cəmi maksimum mənfəət olacaqdır. Bu yanaşma həlli asanlaşdıracaq.

Bunu bu nümunəni götürərək daha aydınlaşdırmaq olar: [1, 7, 2, 3, 6, 7, 6, 7]

Pin

Yuxarıdakı qrafikdən cəmi olduğunu müşahidə edə bilərik $A+B+C$ fərqə bərabərdir $D$ ardıcıl zirvə və vadi yüksəklikləri arasındakı fərqə uyğun gəlir.

Həyata keçirilməsi

Səhmdar C üçün C ++ Proqramı Mənfəəti artırmaq üçün Satış

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

int maxProfit(int prices[], int n) 
{
    int maxprofit = 0;
    for(int i=1;i<n;i++) 
    {
        if(prices[i]>prices[i-1])
            maxprofit+=prices[i]-prices[i-1];
    }
    return maxprofit;
}
    
int main()
{
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   cout<<maxProfit(a,n);
   return 0;
}

Mənfəəti artırmaq üçün Fond Al Satış üçün Java Proqramı Satış

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static int combination(int arr[], int n) 
    { 
        int maxprofit = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1])
                maxprofit += arr[i] - arr[i - 1];
        }
        return maxprofit;
    } 
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int ans = combination(a, n);
        System.out.println(ans);
    }
}

7
65 32 531 1 65 43 876

1396

Mənfəəti artırmaq üçün Satışdan Satış üçün Mürəkkəblik Analizi Satış

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür. Burada yalnız birdəfəlik cavabımızı yeniləyərək bütün massivi gəzirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.