java - Java中使用Kadane算法的子数组的最大总和
问题描述
这是来自极客的问题陈述(链接:https ://practice.geeksforgeeks.org/problems/kadanes-algorithm/0 )
根据编译和测试选项,我的代码运行良好。但是当我尝试提交时,它会引发多个测试用例失败的错误。
谁能帮我解决这个问题?
代码:
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
public class Kadane
{
public static void main(String[]args) throws IOException,NumberFormatException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the number of test cases");
int T = Integer.parseInt(br.readLine());
for(int t=0 ; t<T ; t++)
{
int N,a=0;
int sum1=0,maxsum=-2147483648,kadanesum=-2147483648;
System.out.println("Enter the size of array : ");
N = Integer.parseInt(br.readLine());
int arr[] = new int[N];
System.out.println("Enter the array elements separated by space");
String S = new String(br.readLine());
String elem[] = S.split(" ");
for(String e:elem)
{
arr[a] = Integer.parseInt(e);
a++;
}
for(int i=0 ; i<N ; i++)
{
for(int j=i ; j<N ; j++)
{
sum1 = sum1 + arr[j];
if(maxsum<sum1)
{
maxsum=sum1;
}
}
if(maxsum>kadanesum)
{
kadanesum=maxsum;
}
sum1=0;
maxsum=-2147483648;
}
System.out.println("\tKadane Sum = " + kadanesum);
}
}
}
我的代码链接:https ://ide.geeksforgeeks.org/tXNHh28A0D
我的输入:5(测试用例数)
3(数组大小)
1 2 3(数组元素)
5
1 2 3 -2 5
10
2 9 3 -10 -20 34 28 -50 30 -1
7
4 5 -10 -50 3 9 8
8
8 9 8 -25 25 1 2
我的输出:输入测试用例的数量
输入数组的大小:输入以空格分隔的数组元素 Kadane Sum = 6
输入数组大小:输入以空格分隔的数组元素 Kadane Sum = 9
输入数组的大小:输入以空格分隔的数组元素 Kadane Sum = 62
输入数组大小:输入以空格分隔的数组元素 Kadane Sum = 20
输入数组的大小:输入以空格分隔的数组元素 Kadane Sum = 28
提交代码时收到以下错误消息:
错误的答案。!!!Wrong Answer 可能你的代码在多个测试用例(TCs)中不能正常工作。您的代码失败的第一个测试用例:
输入:(根据网站) 3 1 2 3
其正确输出为:6
我在输入测试用例(测试用例 1)中使用了相同的输入,并且输出与预期相同。
任何人都可以帮助我使用 StringBuffer 优化代码吗?
解决方案
输出应该是总和:
System.out.println(kadanesum);
而不是你写的信息:
System.out.println("\tKadane Sum = " + kadanesum);
正如 Rahul 指出的那样,您还需要删除其他消息,例如:
System.out.println("Enter the array elements separated by space");
推荐阅读
- go - Go:如果初始化可能出错或恐慌,我应该在哪里初始化包级变量?
- reactjs - Syncfusion反应网格服务器端分页错误
- rust - 哈希映射
.entry() 错误与`未声明的类型'Entry'` - python - 如何使用原始 sql 处理一页上的多个搜索字段?
- android - Android根据特定按钮发送意图(带数据)
- javascript - 在嵌套对象键上使用 forEach 反应 javascript
- c++ - 当 `typename T::value_type` 被定义中后面的约束拒绝时,是否应该编译失败?
- node.js - 在开发容器和电子中加载共享库时出错
- arrays - 寻找满足给定约束并在 MATLAB 中提供所需输出的数组的解决方案
- node.js - axios ssl 调用HTTPS