標題:
最大連續子序列和
[打印本頁]
作者:
tonyh
時間:
2023-5-27 20:08
標題:
最大連續子序列和
本帖最後由 tonyh 於 2023-6-10 19:50 編輯
試使用動態規劃法(DP),求最大連續子序列和。
範例輸入 1:-2 1 -3 4 -1 2 1 -5 4
範例輸出 1:6
範例輸入 2:0 -2 3 5 -1 2
範例輸出 2:9
範例輸入 3:-2 11 -4 13 -5 -2
範例輸出 3:20
範例輸入 4:-2 1 -3 4 -1 2 1 -5 4
範例輸出 4:6
範例輸入 5:-2 -3 -1
範例輸出 5:-1
Java
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Ch01 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String raw[];
int maxS, maxV;
Ch01() throws Exception
{
raw=br.readLine().split(" ");
for(int i=0, len=raw.length; i<len; i++)
{
if(i==0)
{
maxS=Integer.parseInt(raw[i]);
maxV=Integer.parseInt(raw[i]);
}else
{
int t=Integer.parseInt(raw[i]);
maxS=Math.max(maxS+t, t);
maxV=Math.max(maxV, maxS);
}
}
System.out.println(maxV);
}
public static void main(String[] args) throws Exception{
new Ch01();
}
}
複製代碼
C++
#include<bits/stdc++.h>
using namespace std;
stringstream ss;
string str;
int maxS, maxV;
int main()
{
cin.tie(0);
cin.sync_with_stdio(0);
getline(cin, str);
ss<<str;
int t;
ss>>t;
maxS=t;
maxV=t;
while(ss>>t)
{
maxS=max(maxS+t, t);
maxV=max(maxV, maxS);
}
cout<<maxV<<endl;
return 0;
}
複製代碼
作者:
王法棣
時間:
2023-6-3 20:59
本帖最後由 王法棣 於 2023-6-4 00:50 編輯
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Ch1 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int q;
int a[];
int max=0;
String raw[];
Ch1() throws Exception
{
raw=br.readLine().split(" ");
a=new int[raw.length+1];
for(int i=1;i<=raw.length;i++)
{
a[i]=a[i-1]+Integer.parseInt(raw[i-1]);
if(Integer.parseInt(raw[i-1])>a[i])
a[i]=Integer.parseInt(raw[i-1]);
}
for(int i=1;i<=raw.length;i++)
{
if(max<a[i])
max=a[i];
}
System.out.println(max);
}
public static void main(String[] args) throws Exception {
new Ch1();
}
}
複製代碼
作者:
陳依彤
時間:
2023-6-3 21:05
#include<bits/stdc++.h>
using namespace std;
int n,sum=0,Max=0;
stringstream ss;
string str;
int main()
{
cin.tie(0);
cin.sync_with_stdio(0);
getline(cin,str);
ss<<str;
while(ss>>n){
if(sum+n>n)sum=sum+n;
else sum=n;
if(Max<sum)Max=sum;
}
cout<<Max;
return 0;
}
複製代碼
作者:
許志捷
時間:
2023-6-3 22:38
#include<bits/stdc++.h>
using namespace std;
int sum,Max,n;
string s;
stringstream ss;
int main()
{
cin.tie(0);
cin.sync_with_stdio(0);
ss.clear();
getline(cin,s);
ss<<s;
while(ss>>n)
{
if((n+sum)>n)
sum+=n;
else
sum=n;
if(Max<sum)
Max=sum;
}
cout<<Max<<"\n";
return 0;
}
複製代碼
作者:
王秉鈞
時間:
2023-6-10 19:42
#include<bits/stdc++.h>
using namespace std;
stringstream ss;
string str;
int n,index=0;
int cMaxSum, fMaxSum;
int main()
{
cin.tie(0);
cin.sync_with_stdio(0);
getline(cin,str);
ss<<str;
while(ss>>n)
{
if(index==0)
{
cMaxSum=n;
fMaxSum=n;
}
else
{
cMaxSum=max(n+cMaxSum,n);
fMaxSum=max(fMaxSum,cMaxSum);
}
index++;
}
cout<<fMaxSum<<endl;
return 0;
}
複製代碼
作者:
張博竣
時間:
2023-6-10 19:44
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Ch1 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int q;
int a[];
int max=0;
String raw[];
Ch1() throws Exception
{
raw=br.readLine().split(" ");
a=new int[raw.length+1];
for(int i=1;i<=raw.length;i++)
{
a[i]=a[i-1]+Integer.parseInt(raw[i-1]);
if(Integer.parseInt(raw[i-1])>a[i])
a[i]=Integer.parseInt(raw[i-1]);
}
for(int i=1;i<=raw.length;i++)
{
if(max<a[i])
max=a[i];
}
System.out.println(max);
}
public static void main(String[] args) throws Exception {
new Ch1();
}
}
複製代碼
作者:
曾元瑜
時間:
2023-6-10 19:45
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Ch01 {
int maxS,maxV;
String raw[];
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Ch01()throws Exception
{
raw=br.readLine().split(" ");
for(int i=0;i<raw.length;i++)
{
if(i==0)
{
maxS=Integer.parseInt(raw[i]);
maxV=Integer.parseInt(raw[i]);
}
else
{
int t=Integer.parseInt(raw[i]);
maxS=Math.max(maxS+t, t);
maxV=Math.max(maxV, maxS);
}
}
System.out.println(maxV);
}
public static void main(String[] args) throws Exception{
new Ch01();
}
}
複製代碼
作者:
許洧熏
時間:
2023-6-10 19:52
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Ch01 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String raw[];
int maxS, maxV;
Ch01() throws Exception
{
raw=br.readLine().split(" ");
for(int i=0, len=raw.length; i<len; i++)
{
if(i==0)
{
maxS=Integer.parseInt(raw[i]);
maxV=Integer.parseInt(raw[i]);
}else
{
int t=Integer.parseInt(raw[i]);
maxS=Math.max(maxS+t, t);
maxV=Math.max(maxV, maxS);
}
}
System.out.println(maxV);
}
public static void main(String[] args) throws Exception{
new Ch01();
}
}
複製代碼
作者:
黃子倢
時間:
2023-6-10 20:00
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class E346 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String raw[];
int maxS, maxV;
E346() throws Exception
{
raw=br.readLine().split(" ");
for(int i=0, len=raw.length; i<len; i++)
{
if(i==0)
{
maxS=Integer.parseInt(raw[i]);
maxV=Integer.parseInt(raw[i]);
}else
{
int t=Integer.parseInt(raw[i]);
maxS=Math.max(maxS+t, t);
maxV=Math.max(maxV, maxS);
}
}
System.out.println(maxV);
}
public static void main(String[] args) throws Exception{
new E346();
}
}
複製代碼
作者:
林土水
時間:
2023-6-10 20:28
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Ch01 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String raw[];
int maxS, maxV;
Ch01() throws Exception
{
raw=br.readLine().split(" ");
for(int i=0, len=raw.length; i<len; i++)
{
if(i==0)
{
maxS=Integer.parseInt(raw[i]);
maxV=Integer.parseInt(raw[i]);
}else
{
int t=Integer.parseInt(raw[i]);
maxS=Math.max(maxS+t,t);
maxV=Math.max(maxV,maxS);
}
System.out.println(maxV);
}
}
public static void main(String[] args)throws Exception{
new Ch01();
}
}
複製代碼
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)
Powered by Discuz! 7.2