C++ Interview preparation questions - Find the maximum sum of subarray in array

Question

I am currently prepping for C++ interview question, by answering some I found on the internet. I don't think my solution is the best, but on the other hand, I am not sure what else would be a better solution, which is why I guess hearing other people's opinion would be great.

Question being:

Given an array of N elements, you are required to find the maximum sum of lengths of all non-overlapping subarrays with K as the maximum element in the subarray.

Example:

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

Here is my solution:

#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;
}

output:

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

output:

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

output:

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

Any way I could make the solution better?..

• Martin R: It seems to me that your algorithm does not work. The only subarray in [9, 9, 7, 0, 0, 9, 4, 2, 4, 5] having K=2as the maximum element is [2], so the result should be 2 and not 11.
• Loser: @MartinR yes you were right.. I messed up the order of two lines.. It should be correct now.
• Martin R: Still looks wrong to me. [9, 9, 2, 0, 3, 6, 0, 1, 5, 6] has no subarray at all with K=4 as the maximum element.
• Loser: @MartinR I am not sure I understand.. In the output example is k=3 And the subarrays are thus {2,0,3} and {0,1} hence max sum is 2+0+3+1+0 = 6
• Martin R: Sorry, my fault. But {0, 1} has the maximum 1 and not 3, so that does not count. – Does your code produce the expected results with all the test cases in practice.geeksforgeeks.org/problems/…?

Answer 1

You haven't shown any of the unit tests. In fact, the way the program is structured (with everything in main()) strongly suggests that there are no unit tests. This immediately reduces confidence in the code.

I'd start by restructuring so we have a simple function to call. I'll make it accept an iterator pair, to act like standard algorithms:

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

We can then write some tests:

#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));
}

(I leave the implementation of TEST_ASSERT_EQUALS() as an exercise - or you can modify to fit your favourite testing framework.)

With the tests in place, we can write a suitable implementation and refine it as we improve the code, with confidence that we're not breaking anything that previously worked.

Answer 2

Reuse the standard algorithms! It will give your code much more expressiveness, and they are very optimized. For example:

#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);
}

• Blasco: Quick question. Why do you need to make the argument of the lamda functions auto&& and not just auto&?
• papagaga: @WooWapDaBug In the context of template deduction, && is what is called a 'universal reference': it will be deduced as a lvalue reference (e.g const int&) if given a lvalue as argument, or a rvalue reference if the argument is passed by value or rvalue (e.g int or object&&). Basically the compiler chooses the right option for you.
• Blasco: But I don't get what's the point there. Isn't find_if passing things by value? can't you just do auto& to get it by reference? I think that the purpose is to avoid a copy, doesn't auto& achieve it? Sorry for my ignorance and thank you for the explanation
• papagaga: @WooWapDaBug No point here, you're right, just a good practice. auto&&does it always right, so why bother choosing the right signature by your self? In other places you could find iterators which don't return lvalue references, like move_iterator.
• papagaga: auto& can't bind to a rvalue reference, so it wouldn't compile I guess