Largest Subarray - Company-specific OAs / Google OA

Problems
1

https://algo.monster/problems/google_oa_largest_subarray

2

I’m not sure if I completely understood the problem.

In the following example:
arr = [300, 80, 40, 300, 42, 31, 56, 300, 80, 42, 300, 523]
k = 4

What would be the largest sub-array?
1: [80, 42, 300, 523]; sum => 945
2: [300, 80, 42, 300]; sum => 722

if the second result is the answer, could you please elaborate on the problem needs to be solved?

3

We’re not comparing the sums, we’re comparing the first value that is different between the arrays with the same index. In your example the first element on array1 is 80, which is different than the first element on array2. Therefore, since 300 > 80 array2 is the larger one.

4

The last test case #7 is incorrect the list display the pattern 500, 499… but the answer is 500 500 500 499 500 499 500 499 500 499.
But no where on this list are there three 500s in a row.
my answer: 500 499 500 499 500 499 500 499 500 499

5

C++ solution:

std::vector get_largest_subarray(std::vector arr, int k) {
auto is_less = [&] (int ai, int bi) {
for (int i = 0; i < k; ++i, ++ai, ++bi) {
if (arr[ai] < arr[bi])
return true;
if (arr[ai] > arr[bi])
return false;
}
return false;
};

int li = 0;
for (int i = 1; i <= arr.size() - k; ++i) {
    if (is_less(li, i))
        li = i;
}

return std::vector<int>(arr.begin() + li, arr.begin() + li + k);

}

6

C++ solution:

std::vector<int> get_largest_subarray(std::vector<int> arr, int k) {
    auto is_less = [&] (int ai, int bi) {
        for (int i = 0; i < k; ++i, ++ai, ++bi) {
            if (arr[ai] < arr[bi])
                return true;
            if (arr[ai] > arr[bi])
                return false;
        }
        return false;
    };
    
    int li = 0;
    for (int i = 1; i <= arr.size() - k; ++i) {
        if (is_less(li, i))
            li = i;
    }
    
    return std::vector<int>(arr.begin() + li, arr.begin() + li + k);
}
7

Is there a better solution than the one posted? If I am not wrong - the posted solution is O(k*n) time