{"id":"417afff3-83e2-4db3-be48-b30c7d8d8a17","name":"Kadane's Algorithm","description":"1. You are given an array(arr) of integers.\r\n2. You have to find maximum subarray sum in the given array.\r\n3. The subarray must have at least one element.","inputFormat":"A number N\r\na1\r\na2.. N integers","outputFormat":"A number representing maximum subarray sum in the given array.","constraints":"1 &lt;= N &lt;= 10000\r\n-2^31 &lt;= arr[i] &lt;= 2^31 - 1 ","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static int solution(int[] arr) {\r\n // write your code here\r\n\r\n return 0;\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < arr.length; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n System.out.println(solution(arr));\r\n }\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n1\r\n2\r\n3","sampleOutput":"6\r\n","questionVideo":"https://www.youtube.com/embed/VMtyGnNcdPw?end=1018","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"b4299fd7-c23e-4326-bdae-18a972fedc52","name":"Kadane's Algorithm","slug":"kadane-s-algorithm","type":1}],"next":{"id":"0ada3a47-e589-476b-81e6-b48bb682896f","name":"Kadane's algorithm MCQ","type":0,"slug":"kadane-s-algorithm-mcq"},"prev":{"id":"60dc2753-727b-498d-8ff6-8fa1d2c7f4f8","name":"Shortest Uncommon Subsequence","type":1,"slug":"shortest-uncommon-subsequence"}}}

Kadane's Algorithm

1. You are given an array(arr) of integers. 2. You have to find maximum subarray sum in the given array. 3. The subarray must have at least one element.

{"id":"417afff3-83e2-4db3-be48-b30c7d8d8a17","name":"Kadane's Algorithm","description":"1. You are given an array(arr) of integers.\r\n2. You have to find maximum subarray sum in the given array.\r\n3. The subarray must have at least one element.","inputFormat":"A number N\r\na1\r\na2.. N integers","outputFormat":"A number representing maximum subarray sum in the given array.","constraints":"1 &lt;= N &lt;= 10000\r\n-2^31 &lt;= arr[i] &lt;= 2^31 - 1 ","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static int solution(int[] arr) {\r\n // write your code here\r\n\r\n return 0;\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < arr.length; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n System.out.println(solution(arr));\r\n }\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n1\r\n2\r\n3","sampleOutput":"6\r\n","questionVideo":"https://www.youtube.com/embed/VMtyGnNcdPw?end=1018","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"b4299fd7-c23e-4326-bdae-18a972fedc52","name":"Kadane's Algorithm","slug":"kadane-s-algorithm","type":1}],"next":{"id":"0ada3a47-e589-476b-81e6-b48bb682896f","name":"Kadane's algorithm MCQ","type":0,"slug":"kadane-s-algorithm-mcq"},"prev":{"id":"60dc2753-727b-498d-8ff6-8fa1d2c7f4f8","name":"Shortest Uncommon Subsequence","type":1,"slug":"shortest-uncommon-subsequence"}}}
plane

Editor


Loading...

Kadane's Algorithm

easy

1. You are given an array(arr) of integers. 2. You have to find maximum subarray sum in the given array. 3. The subarray must have at least one element.

Constraints

1 <= N <= 10000 -2^31 <= arr[i] <= 2^31 - 1

Format

Input

A number N a1 a2.. N integers

Output

A number representing maximum subarray sum in the given array.

Example

Sample Input

3 1 2 3

Sample Output

6

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode