kth max subarrays using kadane's algorithm.

general
1

How to find kth max subarrays using kadane’s algorithm?

2

How about using google ?

3

Kadane’s algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position. The algorithm only needs to keep track of the ending position because the implied starting position is just after the last position at which the sum went negative; a higher sum can always be found by dropping any negative-sum prefix. Thus, the problem can be solved with the following code, expressed here in Python:

def max_subarray(A):
max_ending_here = max_so_far = 0
for x in A:
    max_ending_here = max(0, max_ending_here + x)
    max_so_far = max(max_so_far, max_ending_here)
return max_so_far

A variation of the problem that does not allow zero-length subarrays to be returned, in the case that the entire array consists of negative numbers, can be solved with the following code:

def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A[1:]:
    max_ending_here = max(x, max_ending_here + x)
    max_so_far = max(max_so_far, max_ending_here)
return max_so_far
1 Like
4

how to solve this using kadane algorithm : https://www.codechef.com/problems/KTHMAX

5

@rashedcs: I’m not sure if you can solve that with Kadane’s algorithm. Check out my post on this. I have explained the approach. https://www.facebook.com/algo0111/posts/142352516249980

1 Like
6

I can’t find your post on FB

7

Here’s a successful code in

lang-c++14

#include
#include
#include
#include

int main()
{
int testCases;
std::cin >> testCases;

while(testCases--) {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> nums(n);
    std::vector<std::pair<int, int> > indexMap(n);
    std::set<int> bounds;
    std::vector<long long> ranges(n);

    for (int i=0;i<n;i++) {
        std::cin >> nums[i];
        std::pair<int, int> p(nums[i], i);
        indexMap[i] = p;
    }

    // Sort indexMap.  It will contain all the nums in sorted order,
    // with a map to the original index.
    std::sort(indexMap.begin(), indexMap.end());

    long long numUsed = 0;
    bounds.insert(-1);
    bounds.insert(n);
    for (int i=n-1; i>=0; i--) {
        int index = indexMap[i].second;
        int low   = *(--bounds.lower_bound(index));
        int high  = *(bounds.upper_bound(index));
        long long count = (long long) (index - low) * (high - index);

        bounds.insert(index);
        numUsed += count;
        ranges[n-1-i] = numUsed;
    }

    for (int i=0;i<m;i++) {
        long long query;
        int qIndex;
        int result;

        std::cin >> query;
        qIndex = std::lower_bound(ranges.begin(), ranges.end(), query) -
                    ranges.begin();
        result = indexMap[n-1-qIndex].first;
        std::cout << result << std::endl;
    }
}
return 0;

}

1 Like
8

oustanding Dr DC Shetty it

9

Tnq bro…Please tell me - how to solve it???