Home/

...

/

Solution Review: Maximum Sum Subarray

Solution Review: Maximum Sum Subarray

This review discusses the solution to the "Maximum Sum Subarray" challenge in detail.

Solution (Kadane’s algorithm)

This algorithm takes a dynamic programming approach to solving the maximum subarray sum problem. Take a look at the algorithm.

Press + to interact
fn max_sum_arr(arr: &[i32]) -> i32{
    let mut count = arr[0]; 
    let mut mx = arr[0];
    for i in 1..arr.len(){
        if count < 0 {
            count = arr[i];
        }
        else {
            count += arr[i];
        }
        if mx < count{
            mx = count;
        }
    }
    mx
}

The basic idea of “Kadane’s algorithm” is to scan the entire array. At each position, find the maximum sum of the subarray ending there. This is achieved by keeping a count for the current array index and a mx. The algorithm is as follows:

 ...
Access this course and 1200+ top-rated courses and projects.
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy