如何降低c++的时间复杂度

Question

当给定 n 个整数时，您可以将两个数字相乘或保持原样。我编写了一个算法来查找所有值相加的最大值。

例如输入为：

9(数组长度) -1 -8 2 1 3 6 -5 0 1

输出需要是62：

62=-8x-5+0x-1+6x3+2+1+1

如果数组为 7 4 1 2 5 3 1 9 0，则答案应为 91。如果数组为 -13 7 -12 13 -8 4 12 7 15 6 -2 10 9 15 4 1 -15，则答案应为应该是838。

我的代码是这样的： sth.cpp

#include <iostream>
#include <fstream>
#include "sop.h"
using namespace std;

int main(int argc, char* argv[]) {
    int i = 0;
    int num = 0;
    int* array = NULL;
    ifstream fin;
    sop* _sop = NULL;

    if (argc > 1) {
        fin.open(argv[1]);
        if (!fin.is_open()) {
            cerr << "File " << argv[1] << " does not exist!" << endl;
            exit(0);
        }
        fin >> num;
        array = new int[num];
        for (i = 0;i < num;i++)        fin >> array[i];
        fin.close();
    }
    else {
        cin >> num;
        array = new int[num];
        for (i = 0;i < num;i++)        cin >> array[i];
    }

    _sop = new sop(array, num);
    cout << "Input array: ";
    _sop->printArray();
    cout << "Maximum sum of products = " << _sop->maxSOP() << endl;
    delete _sop;
    if (array)       delete[] array;
    array = NULL;
    return 0;
}

sth.h（标头）

#pragma once
#ifndef __SOP_H__
#define __SOP_H__

class sop {
private:
    int num;
    int* array;

    // Declare member variables or functions here if you need...

public:
    sop();
    sop(int* a, int n);
    ~sop();

    void printArray(void);
    int maxSOP(void);
};

#endif

sop.cpp

#include <iostream>
#include "sop.h"
using namespace std;

sop::sop() {
    this->num = 0;
    this->array = NULL;
}
sop::sop(int* a, int n) {
    int i = 0;
    this->num = n;
    this->array = new int[n];
    for (i = 0; i < n; i++)        this->array[i] = a[i];
}
sop::~sop() {
    if (this->array) {
        if (num > 1)       delete[] array;
        else    delete array;
    }
    this->num = 0;
    this->array = NULL;
}
void sop::printArray(void) {
    int i = 0;
    if (!this->num)  return;
    for (i = 0; i < num; i++)      cout << array[i] << "  ";
    cout << endl;
}
int sop::maxSOP(void) {
    for (int i = 0; i < this->num - 1; ++i)
    {
        int min_index = i;
        
        for (int j = i + 1; j < this->num; ++j)
        {
            if (this->array[j] < this->array[min_index])
            {
                min_index = j;
            }
        }

        int temp = this->array[min_index];
        this->array[min_index] = this->array[i];
        this->array[i] = temp;
    }

    int sum = 0;
    int i = 0;

    for (; i + 1 < this->num && this->array[i + 1] <= 0; i += 2) 
    {
        sum += this->array[i] * this->array[i + 1];
    }
    
    for (; i < this->num && this->array[i] <= 1; ++i) 
    {
        sum += this->array[i];
    }

    for (int j = this->num - 1; j > i; j -= 2) 
    {
        sum += this->array[j] * this->array[j - 1];
    }
    
    if ((this->num - i) % 2 == 1) {
        sum += this->array[i];
    }

    return sum;
}

在 sop.cpp 中，maxSOP 函数的时间复杂度为 O(n^2)，如何在不添加任何其他库的情况下将时间复杂度降低为 O(n) 或 O(nlogn)

Answer 1

ف٠٢٠ف ففففففففف ففففففففففففففففففففف