Үр дагаврыг нэмэгдүүлэх хамгийн дээд хэмжээ


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Фанатикууд Microsoft- Morgan Stanley
Array Динамик програмчлал

Асуудлын мэдэгдэл

Танд массив бүхэл тоонууд. Таны даалгавар бол массив доторх хамгийн их нийлбэр дарааллыг дараах дарааллын тоог дарааллаар нь дарааллаар нь олох дарааллаар олох явдал юм. эрэмбэлсэн нэмэгдэж буй дэг журам. Дараалал гэдэг нь эхний массиваас зарим элементүүдийг хасвал бидний олж авах дараалалаас өөр зүйл биш юм.

Жишээ нь

arr[] = {2,4,5,10,1,12}
33

Тайлбар: {2, 4, 5, 10, 12} -н нийлбэр ⇒ 33. Бид эрэмбэлэгдсэн нөхцлийг хангахын тулд 4-р индекс дээрх элементээс бусад анхны оролтын массивыг бүхэлд нь авав (0-д суурилсан индексжүүлэх). Энэ дараалал нь бидэнд хамгийн сайн үр дүнг өгдөг. Бусад аливаа дараалал нь одоогийн нийлбэрээс бага нийлбэрт хүргэнэ.

arr[] = {3,5,7,1,20,4,12}
35

Тайлбар: {3, 5, 7, 20} -н нийлбэр ⇒ 35. Энд массивын үлдсэн хэсгийг эрэмбэлсэн 1 ба 4-ийг хасав. Дараа нь үлдсэн элементүүд нь хамгийн их нийлбэрийг нэмэгдүүлдэг.

 

Хамгийн их нийлбэрийг нэмэгдүүлэх алгоритм

1. Declare an array say maxSumIS as the same size as the length of an array.
2. Set the output to 0.
3. Copy each element of an array into the created array.
4. Traverse the array from i=1 to i<n(length of the array)
  Now in another loop, from j=0 to j<i,
    Check if arr[i] is greater than arr[j] and maxSumIS[i] is less than maxSumIS[j]+arr[i]N,
      Then update the value of maxSumIS[i] = maxSumIS[j] + arr[i].
5. Traverse the array, and find out the maximum of all the elements from maxSumIS and return that value.

 

Тайлбар

Бид эрэмбэлэх эсвэл ангилах боломжгүй бүхэл тоон массивыг өгсөн. Бид хамгийн их нийлбэрийг нэмэгдүүлэх дарааллыг олохыг хичээдэг. Энэ нь бас нэмэгдэж буй дараалалд байх ёстой. Тиймээс бид өгөгдсөн массивтай ижил хэмжээтэй массив үүсгэх болно. Дараа нь бид гаралтыг 0 гэж тохируулсан болно. Энэ гаралтын утга нь бүх элементүүдийн дунд хамгийн дээд хэмжээг олоход туслах болно.

Бид массивыг анх удаа туулах болно. Эхний удаа тухайн массивын утгыг бидний үүсгэсэн массив руу хуулах болно maxSumIS []. энэ нь maxSumIS [] массив нь бидний нөхцөл хангагдах бүрт шинэчлэгддэг. Тиймээс maxSumIS массив дахь эхний индексийг ашиглах гэж байгаа тул бид эхлээд массивыг i = 1-ээс туулах болно. Тиймээс л бид хоёр дахь давталтын утгыг 0-ээс i-д шилжүүллээ. Бид нөхцөл байдлыг шалгах гэж байна хэрэв arr [i] arr [j] -аас их байвал, мөн maxSumIS [j] нь одоогийн i ба j индексүүдийн дагуу өмнөх хоёр элементийн нийлбэрээс бага байна. Хэрэв хоёр нөхцөл хангагдсан бол maxSumIS [i] -н утгыг maxSumIS [j] ба arr [i] гэж одоогийн хоёр индексийн элементийн нийлбэр болгон шинэчилнэ.

Учир нь бид зөвхөн хамгийн их нийлбэрийн дарааллыг зөвхөн өсөх дарааллаар олохыг хүсч байгаа тул хоёр элементийг зэрэг авч байгаа юм.

Үүний дараа бид maxSumIS массивт хадгалсан болон шинэчилсэн бүх элементүүдийнхээ дээд хэмжээг олж мэдэх ёстой. Бид массивыг бүхэлд нь туулах эсвэл ямар ч функцийг ашиглан хамгийн их тоог олох боломжтой. Гэхдээ бид maxSumIS массивын бүх элементүүдийн хамгийн их тоог буцааж өгөх хэрэгтэй.

Үр дагаврыг нэмэгдүүлэх хамгийн дээд хэмжээ

Дээд хэмжээг нэмэгдүүлэх үр дагаварын код

C ++ код

#include<iostream>
using namespace std;

int getMaximumSumIS(int arr[], int n)
{
    int i, j, output = 0;
    int maxSumIS[n];

    for ( i = 0; i < n; i++ )
        maxSumIS[i] = arr[i];

    for ( i = 1; i < n; i++ )
        for ( j = 0; j < i; j++ )
            if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                maxSumIS[i] = maxSumIS[j] + arr[i];

    // Take the maximum out of all the possible answers
    for ( i = 0; i < n; i++ )
        if ( output < maxSumIS[i] )
            output = maxSumIS[i];

    return output;
}
int main()
{
    int arr[] = {2,4,5,10,1,12};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Total sum of Maximum Sum Increasing Subsequence : " << getMaximumSumIS( arr, n );
    return 0;
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

Java код

class MaximumSumIncreasingsubsequence
{
    public static int getMaximumSumIS(int arr[], int n)
    {
        int i, j, output = 0;
        int maxSumIS[] = new int[n];

        for (i = 0; i < n; i++)
            maxSumIS[i] = arr[i];

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                    maxSumIS[i] = maxSumIS[j] + arr[i];

        // Take the maximum out of all the possible answers
        for (i = 0; i < n; i++)
            if (output < maxSumIS[i])
                output = maxSumIS[i];

        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2,4,5,10,1,12};
        int n = arr.length;
        System.out.println("Total sum of Maximum Sum Increasing Subsequence : "+getMaximumSumIS(arr, n));
    }
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Эндээс хойш бид хоёр гогцоотой байна 0-ээс n-1 хүртэл болон дотоод гогцоо 0 to i. Тиймээс алгоритм нь цаг хугацааны олон гишүүнт төвөгтэй байдаг. O (n2хаана "N" массив дахь элементүүдийн тоо юм.

Сансрын нарийн төвөгтэй байдал

Энд бидэнд асуудалд шугаман орон зайн төвөгтэй байдлыг бий болгож буй n хэмжээтэй 1D массив л байна. O (N) хаана "N" массив дахь элементүүдийн тоо юм.