0
votes

Comment réduire la complexité du temps de cette solution en C ++?

Compte tenu d'un tableau d'entier nums, trouvez la sous-réseau contiguë (contenant au moins un nombre) qui a la somme la plus importante et renvoie sa somme. P>
Exemple: P>
Entrée: [-2,1, -3,4, -1,2,1, -5,4], Sortie: 6 Explication: [4, -1,2,1] a la plus grande somme = 6. P>
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        
        int max=INT_MIN;
        int result;
        int i,j;
        if(nums.size()==1)
            return nums[0];
        if(nums.size()==0)
            return 0;
        for(i=0;i<nums.size();i++)
        {
            
            for(j=i;j<nums.size();j++)
            {
                
                result=accumulate(nums.begin()+i,nums.begin()+j+1,0);
                if(result>max)
                    max=result;
                
            }
            
        }
        return max;
    }
};

algorithm c++ data-structures vector dsa

3 commentaires

Ceci lit comme il s'agit d'un site de concours / défi / site de codage / piratage compétitif. Est-ce? Si votre objectif est d'apprendre C ++, vous n'en apprendrez rien. Dans presque tous les cas, comme celui-ci, la solution correcte est basée sur une astuce mathématique ou de programmation. Si vous ne savez pas ce que l'astuce est et essayez de coder une approche de force brute, le programme est lent et échoue pour cette raison. Si vous essayez d'apprendre C ++, vous n'apprendrez rien des sites de concours en ligne sans signification Mais seulement à partir d'un bon manuel C ++ .

Vous «optimiserez» en utilisant un algorithme différent. (Cela ressemble à un problème de programmation dynamique, alors je commencerais là.)

Oui, je pensais que c'est un problème DP, cherche juste une façon de le résoudre pour le temps donné sans utiliser dp

3 Réponses :

0
votes

ci-dessous est réalisé en une seule boucle, de un des premiers résultats Googled . Avec une petite comptabilité, vous pouvez également contenir les postes de premier et dernier élément de la plus grande subséquence avec la Somme max_so_far code>.

    #include<iostream> 
    #include<climits> 

    using namespace std; 

    int maxSubArraySum(int a[], int size) 
    { 
        int max_so_far = INT_MIN, max_ending_here = 0; 

        for (int i = 0; i < size; i++) 
        { 
            max_ending_here = max_ending_here + a[i]; 
            if (max_so_far < max_ending_here) 
                max_so_far = max_ending_here; 

            if (max_ending_here < 0) 
                max_ending_here = 0; 
        } 
        return max_so_far; 
   }

0 commentaires

0
votes

regarder ce lien: https://www.geeksforgeeks.org/ Sous-carratage /

Couple de solutions efficaces là-bas.

Idée principale est de garder une variable maxsum, qui gardera une trace de la somme maximale vue jusqu'à présent. Vous avez également besoin d'une variable Courrentsum qui garde une trace de la somme dans la fenêtre actuelle. Chaque fois que vous ajoutez un nombre positif à la somme actuelle, comparez-la à maxsum et à la mise à jour maxsum si les courantsum> maxsum.

0 commentaires

1
votes

Ceci peut être fait en utilisant Algorithme de Kadane .

#include<algorithm> //this header file is required for max function.
class Solution
{
public:
    int maxSubArray(vector<int>& nums) {
        int temp=0;
        int max_sum=0;
        for(int i=0;i<nums.size();i++)
        {
            temp=max(temp+nums[i],nums[i]);
            max_sum=max(temp,max_sum);
        }
        return max_sum;
    }
};

0 commentaires