Maximum subarray sum codewars python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

gibranpulga/MaximumSubarraySumKata-codewars

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

Max.sequence(new int[]); // should be 6: Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

Источник

CodeWars 5kyu Maximum subarray sum

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])

// should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

Requirement

1. Should return maximum sum of any subarrays including empty list.
2. Return 0 when all of list’s element is negative numbers.

Solution

I used Dynamic Programming — Bottom up approach to solve this problem. Because I learned on some online lectures about Dynamic Programming recently.

1. First I catched that all the start and end element in subarray is positive numbers. So I decided to put all positive numbers’ index in positive_index list.
2. Make a 2 dementional array, sum[][] to keep the sum of subarrays.
3. Drew the recurrance Induction of this problem.
   • Basis
     • sum[i][i] = arr[positive_index[i]]
     • sum[i][i+1] = arr[positive_index[i]] to arr[positive_index[j]] (i < positive_index.length - 1)
   • Inductive Step
     • sum[i][j] = sum[i][j-1] + sum[j-1][j] — arr[positive_index[j-1]]

javaScript Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var maxSequence = function(arr){
var positive_index = []

arr.filter(function positive_check(element, index){
if(element>0){
positive_index.push(index);
}
})

if (positive_index.length == 0) return 0;

var sum = Array(positive_index.length).fill(null).map(() => Array(positive_index.length));
var max = Number.MIN_SAFE_INTEGER;

for(var i=0; i
sum[i][i] = arr[positive_index[i]];
if(max < sum[i][i]){
max = sum[i][i];
}
if(i+1 sum[i][i+1] = arr.slice(positive_index[i], positive_index[i+1]+1).reduce((a,b)=>a+b);
if(max < sum[i][i+1]){
max = sum[i][i+1];
}
}
}

for(var i=0; i< positive_index.length; i++){
for(var j=i+2; j< positive_index.length; j++){
sum[i][j] = sum[i][j-1] + sum[j-1][j] — arr[positive_index[j-1]];
if(max < sum[i][j]){
max = sum[i][j];
}
}
}
return max;
}

PPT slides

Made presentations for my algorithm study group

Источник

Weekly Coding Challenge: Maximum Subarray Sum using a version of Kadane’s Algorithm – written in Python

2 min read ~ Hello readers! It’s really important for me to continue my practice and learning. Every week, I block off 30 minutes, set a timer and choose a challenge from codewars. This helps me keep my skills sharp, see how other devs all over the planet would solve these problems, and take some leisure time to problem solve and be creative. Being able to see other solutions expands my mind for solving future problems in a clever and efficient way. Today, the problem set focuses on Python.

For those that are not familiar, this challenge uses a version of Kadane’s algorithm (one of my favorites!). If you are not familiar, this algorithm falls within the field of dynamic programming. This algorithm will help us find the largest sum possible in a continuous array of integers that can include negative numbers. Here is a link to learn more.

The maximum sum subarray problem consists in finding the maximum sum of a continuous subarray of integers that can include negative integers:

max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) # should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

def max_sequence(arr): curSum = 0 curMax = 0 for numb in arr: tempNumb = int(numb) if (tempNumb + curSum > 0): curSum = curSum + tempNumb if curSum > curMax: curMax = curSum else: curSum = 0 return curMax

When looking to define the max sequence, we can utilize our curSum to to determine when the sum of integers remains above 0. When that changes, we can check to see if that number is greater than the current max and replace it if necessary. If the number within the iteration added to the curSum falls into a negative number, we know that we are ready to reset our curSum back to 0 and continue with the procedure.

All solutions are also now on my GitHub profile if you want to check out all of the coding challenges I’ve completed so far!

All credit to problem sets goes to codewars

Источник

[Codewars #61] Maximum subarray sum (5kyu)

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

maxSequence [-2, 1, -3, 4, -1, 2, 1, -5, 4] -- should be 6: [4, -1, 2, 1] 

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

My Solution​

public static class Kata    public static bool IsAllNativeInteger(int[] arr)   for (int i = 0; i  arr.Length; i++)   if (arr[i] >= 0)   return false; > > return true; >  public static int MaxSequence(int[] arr)   if (arr == null || arr.Length == 0 || IsAllNativeInteger(arr))   return 0; >  int maxSum = 0; for (int i = 0; i  arr.Length; i++)   int max = 0; for (int j = i; j  arr.Length; j++)   max += arr[j]; if (max > maxSum)   maxSum = max; > > >  return maxSum; > > 

• 5kyu 문제 자체는 상당히 짧은데 생각해야 되는 것들이 좀 있다.
• 일단 가장 먼저 생각난건 처음부터 연속된 숫자를 조회하면서 가장 큰 수가 나올때 까지 계속 수를 더해 가는 방법.
• 이 방법 이외의 방법은 딱히 생각 나지 않는다.

Best Practices​

public static class Kata   public static int MaxSequence(int[] arr)   int max = 0, res = 0, sum = 0; foreach(var item in arr)   sum += item;  max = sum > max ? max : sum;  res = res > sum - max ? res : sum - max; > return res; > > 

Источник

Русские Блоги

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

Max.sequence(new int[]); // should be 6:

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

Динамическая тема планирования, я всегда чувствую? Спросите непрерывную и наибольшую ценность, если вы не знакомы с динамическим планированием, вы можете попытаться использовать двумерное количество групп, а также хорошее упражнение.

Код доллара:

public class Max < public static int sequence(int[] arr) < int len = arr.length; if(len == 0)return 0; if(len == 1)return arr[0] >0 ? arr[0] : 0; //int[] dp = new int[len]; //dp[0] = arr[0] > 0 ? arr[0] : 0; int dp = arr[0] > 0 ? arr[0] : 0; int max = arr[0] > 0 ? arr[0] : 0; for(int i = 1; i < len; i++)< if(arr[i] >0) < //dp[i] = arr[i] + dp[i - 1]; dp += arr[i]; >else < //max = max >dp[i - 1] ? max : dp[i -1]; //dp[i] = dp[i - 1] + arr[i] > 0 ? dp[i - 1] + arr[i] : 0; max = max > dp ? max : dp; dp = dp + arr[i] > 0 ? dp + arr[i] : 0; > > //return max > dp[len - 1] ? max : dp[len - 1]; return max = max > dp ? max : dp; > >

import org.junit.Test; import static org.junit.Assert.assertEquals; public class MaxSequenceTest < @Test public void testEmptyArray() throws Exception < assertEquals("Empty arrays should have a max of 0", 0, Max.sequence(new int[]<>)); > @Test public void testExampleArray() throws Exception < assertEquals("Example array should have a max of 6", 6, Max.sequence(new int[])); > @Test public void testNegativeExampleArray() throws Exception < assertEquals("Example array with all negative values should have a max of 0", 0, Max.sequence(new int[])); > @Test public void testRandomArrays() throws Exception < for(int i = 0; i < 50; i++) < int[] rand = randArr((int)(Math.random() * 10 + 50)); assertEquals("Random array solution not as expected: ", solution(rand), Max.sequence(rand)); >> private int[] randArr(int size) < int[] rand = new int[size]; for(int i = 0; i < size; i++) rand[i] = (int)(Math.random() * 60 - 30); return rand; >private int solution(int[] arr) < int m = 0, a = 0, s = 0; for(int e : arr) < s += e; m = Math.min(s, m); a = Math.max(a, s - m); >return a; > >

Персональное резюме:

Массив динамического планирования заменяется значением, сохраняя пространство памяти.

Источник