計算連續元素（列表中的）最大的總和

Question

我試圖計算矢量 的連續元素的最大總和，但我真的不知道該怎麼辦：

我開始代碼即：

#include <iostream> 
#include <vector> 
using namespace std; 

void calcule_somme(vector<int> tab); 

void calcule_somme(vector<int> tab) { 

    int somme_partielle(0); 
    vector<int> element_les_plusgrand; 

    for(size_t i(0);tab.size();++i) { 

     for(size_t j(i+1);tab.size();++i) { 
       element_les_plusgrand.pushback(tab[i]); 

       if (tab[i]+tab[j]>compteur) { 
        element_les_plusgrand.push_back(tab[j]); 
        compteur = tab[i]+tab[j]; 
       } 


} 







int main() { 





    return 0; 
}` 

的函數必須返回：連續元素的最大和爲「4,5,78」至極等於87

感謝您的幫助

Answer 1

首先，您需要跟蹤兩個向量，一個保存最大的字符序列，一個保存當前正在計算的值。

從那裏，你只需要遍歷源矢量中的元素，跟蹤矢量中的前一個值和當前值。

如果當前值大於先前值，則將當前值推入當前向量，然後將先前值分配給當前值。

如果小於（或者我假設等於），則連續序列完成，您應該從下一個序列開始。這意味着，你需要做到以下幾點：

1. 確定當前矢量的大小大於或等於最大的矢量的大小和電流矢量的總和比最大的總和。如果是，則分配最大=當前;
2. 清除當前列表
3. 分配前一個當前的int值。

這裏是我會怎麼寫呢：

int sum(const vector<int>& tab) { 
    int sum = 0; 
    for (size_t i = 0; i < tab.size(); i++) { 
     sum += tab[i]; 
    } 

    return sum; 
} 

vector<int> calculate_some(const vector<int>& tab) { 
    vector<int> ret, current; 

    int previous = tab[0]; 
    current.push_back(previous); 
    for (size_t i = 1; i < tab.size(); i++) { 
     current.push_back(tab[i]); 

     if (tab[i] <= previous || i == (tab.size() - 1)) { 
      if (current.size() >= ret.size() && sum(current) > sum(ret)) 
       ret = current; 

      current.clear(); 
     } 

     previous = tab[i]; 
    } 

    return ret; 
} 

這裏是我如何打電話吧：

int main() { 

    vector<int> tab = { -4,5,6,-9,24,-35,4,5,78 }; 
    vector<int> results = calculate_some(tab); 

    for (size_t w(0); w<results.size(); ++w) { 
     cout << results[w] << " "; 
    } 

    system("pause"); 


    return 0; 
} 

Answer 2

#include <iostream> 
#include <vector> 
using namespace std; 







int sum(const vector<int>& tab) { 
    int sum = 0; 
    for (size_t i = 0; i < tab.size(); i++) { 
     sum += tab[i]; 
    } 

    return sum; 
} 

vector<int> calculate_sume(const vector<int>& tab) { 
    vector<int> ret, current; 

    int previous = -32767; 
    for (size_t i = 0; i < tab.size(); i++) { 
     if ((tab[i] > previous) == false) { 
      if (current.size() >= ret.size() && sum(current) > sum(ret)) 
       ret = current; 

      current.clear(); 
     } 

     current.push_back(tab[i]); 
     previous = tab[i]; 
    } 
    for(size_t w(0);w<ret.size();++w) { 
     cout << ret[w]<< " "; 
    } 
    return ret; 
} 


int main() { 

    vector<int> tab ={-4,5,6,-9,24,-35,4,5,78}; 
    sum(tab); 
    calculate_sume(tab); 





    return 0; 
} 

告訴我-4 5 6

Answer 3

僞代碼：

Algorithm Biggest_Consecutive_Sum 
Input: Vector v 
Output: Biggest_Sum 

begin 

    index = 0, Biggest_Sum = 0 

    while(index < v.size()){ 

     Sum = 0 

     while (Sum + V[index] > Sum){ 
      Sum = Sum + V[index] 
      index = index + 1 
     } 

     if(Sum > Biggest_Sum) Biggest_Sum = Sum 

     index = index + 1 
    } 

    return Biggest_Sum 

end