C++面试准备问题--寻找数组中子数组的最大和

Question

我目前正在准备C++的面试问题，回答有些是我在网上找到的。我不认为我的解决方案是最好的，但另一方面，我不知道还有什么更好的解决方案，这就是为什么我认为听取别人的意见将是伟大的。

问题是：

给定一个N元素数组，您需要找到所有不重叠子数组的最大长度之和，其中K是子数组中的最大元素。

示例：

Input : arr[] = {2, 1, 4, 9, 2, 3, 8, 3, 4} 
        k = 4
Output : 5
{2, 1, 4} => Length = 3
{3, 4} => Length = 2
So, 3 + 2 = 5 is the answer

这是我的解决方案：

#include <stdio.h>
#include <random>
#include <iostream>
#include <vector>
#include <algorithm>

int main() {

  std::random_device rd;  
  std::mt19937 gen(rd()); 
  std::uniform_int_distribution<int> distribution(0,9);

  int arr[10];

  int  k = distribution(gen);
  for (int i = 0; i < 10; ++i)
  {
      arr[i] = distribution(gen);;
      std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
  std::cout << "K: " << k << std::endl; 

  std::vector<int> start_index;
  std::vector<int> end_index;
  std::vector<int> sum;

    for (int i = 0; i<10; ++i)
    {
        int subarray_sum = 0;  
        if(arr[i] <= k)
        {
            start_index.push_back(i);
            subarray_sum += arr[i];
            ++i;
            while(arr[i] <= k && i<10) 
            {
                subarray_sum += arr[i];
                ++i;
            }
            end_index.push_back(i-1);
            sum.push_back(subarray_sum);
            std::cout << "sum: " << subarray_sum << std::endl; 
        }
    }

  std::cout << "length of sums: " << sum.size() << std::endl;
  std::cout << "number of start_index: " << start_index.size() << std::endl; 
  std::cout << "number of end_index: " << end_index.size() << std::endl; 

  std::cout << "-------------Compute max subarray_sum length-----------------" << std::endl; 
  if(sum.size() > 1)
  {
    std::vector<int>::iterator iterator1 = std::max_element(sum.begin(),sum.end());
    int position1 = iterator1 - sum.begin();
    std::cout << position1 << std::endl; 

    int length1 = end_index[position1]- start_index[position1]+1; //+1 because they don't zero-index

    sum.erase(sum.begin() + position1);
    start_index.erase(start_index.begin() + position1);
    end_index.erase(end_index.begin()+position1);

    std::cout << "length of sums: " << sum.size() << std::endl;
    std::cout << "number of start_index: " << start_index.size() << std::endl; 
    std::cout << "number of end_index: " << end_index.size() << std::endl; 


    std::vector<int>::iterator iterator2 = std::max_element(sum.begin(),sum.end());
    int position2 = iterator2 - sum.begin();
    std::cout << position2 << std::endl; 

    int length2 = end_index[position2]- start_index[position2]+1; //+1 because they don't zero-index


    sum.erase(sum.begin() + position2);
    start_index.erase(start_index.begin() + position2);
    end_index.erase(end_index.begin()+position2);

    std::cout << "length1: " << length1 << " " << std::endl 
              << "length2: " << length2 << std::endl 
              << "legnth Sum: " << length1 + length2 << std::endl; 


  }
  else if ( sum.size() == 1)
  {
    std::vector<int>::iterator iterator1 = std::max_element(sum.begin(),sum.end());
    int position1 = iterator1 - sum.begin();
    std::cout << position1 << std::endl; 

    int length1 = end_index[position1]- start_index[position1]+1; //+1 because they don't zero-index
    std::cout << "max length sum: " << length1 << std::endl;

  }

  else
  {
    std::cout << "None fit criteria" << std::endl; 
  }
    return 0;
}

产出：

2 3 0 7 5 8 5 5 4 8 
K: 0
sum: 0
length of sums: 1
number of start_index: 1
number of end_index: 1
-------------Compute max subarray_sum length-----------------
0
max length sum: 1

产出：

2 3 4 1 8 0 0 0 1 4 
K: 4
sum: 10
sum: 5
length of sums: 2
number of start_index: 2
number of end_index: 2
-------------Compute max subarray_sum length-----------------
0
length of sums: 1
number of start_index: 1
number of end_index: 1
0
length1: 4 
length2: 5
legnth Sum: 9

产出：

5 1 7 5 2 6 1 4 0 9 
K: 4
sum: 1
sum: 2
sum: 5
length of sums: 3
number of start_index: 3
number of end_index: 3
-------------Compute max subarray_sum length-----------------
2
length of sums: 2
number of start_index: 2
number of end_index: 2
1
length1: 3 
length2: 1
legnth Sum: 4

有什么办法能让解决办法更好吗..

Answer 1

您还没有显示任何单元测试。事实上，程序的结构方式(包括main()中的所有内容)强烈地表明没有单元测试。这立即降低了对代码的信心。

我从重组开始，这样我们就可以调用一个简单的函数了。我将让它接受一个迭代器对，以类似于标准算法：

#include <cinttypes>

template<typename ForwardIterator, typename Value>
std::size_t total_length_of_segments_having_max_value(ForwardIterator first, ForwardIterator last, const Value& value);

然后我们可以编写一些测试：

#include <vector>

int main()
{
    const std::vector<int> v1{ 2, 1, 4, 9, 2, 3, 8, 3, 4 };
    auto const first = v1.begin();
    auto const last = v1.end();

    // start by testing an empty input
    TEST_ASSERT_EQUALS(0, total_length_of_segments_having_max_value(first, first, 2));

    TEST_ASSERT_EQUALS(5, total_length_of_segments_having_max_value(first, last, 4));
    TEST_ASSERT_EQUALS(0, total_length_of_segments_having_max_value(first, last, 10));
}

(我将TEST_ASSERT_EQUALS()的实现作为练习--或者您可以修改以适应您最喜欢的测试框架。)

在测试就绪之后，我们可以编写一个合适的实现，并在改进代码时对其进行改进，并有信心我们不会破坏以前的任何工作。

Answer 2

重用标准算法！它将为您的代码提供更多的表现力，并且它们非常优化。例如：

#include <algorithm>
#include <iterator>
template <typename Iterator>
int max_subsets_length_with_max(Iterator first, Iterator last, int k) {
    auto begin_subset = std::find_if(first, last, [k](auto&& elem) { return elem <= k; });
    if (begin_subset == last) return 0;
    auto end_subset = std::find_if(begin_subset, last, [k](auto&& elem) { return elem > k; });
    if (std::find(begin_subset, end_subset, k) != end_subset) {
        //std::cout << "subset [" << *begin_subset << " , " << *end_subset << "]\n";
        return std::distance(begin_subset, end_subset) + max_subsets_length_with_max(end_subset, last, k);
    }
    return max_subsets_length_with_max(end_subset, last, k);
}